Counting 'zzy' Subsequences

After failing his math exam repeatedly, zzy has stopped paying attention in math class and now scribbles random strings on his scrap paper. In one such instance, he writes a strange string and then decides to "enjoy" himself by counting how many subsequences equal to zzy appear in the string. Note that a subsequence does not necessarily consist of consecutive characters, unlike a substring.

You are required to count the number of subsequences that form the string zzy in the given string. You can use the following dynamic programming approach:

Let \( dp[i] \) be the number of ways to form the prefix of the target string T up to position \( i \) (with \( dp[0] = 1 \)). Then, when processing a character \( s[j] \) in the input string, update:

\[ \text{if } s[j] = T[i] \text{ then } dp[i+1] = dp[i+1] + dp[i] \]

Here, \( T = \text{\"zzy\"} \) and the final answer is \( dp[3] \).

inputFormat

The input consists of a single line, a string \( S \) made up of lowercase English letters. The string can be very long.

outputFormat

Output a single integer representing the number of subsequences in \( S \) that equal zzy. It is guaranteed that the output fits in a 64-bit integer.

sample

zzy

1