Description

After failing math exams consecutively, zzy stopped paying attention in math class (in fact, he never really did). He starts doodling on scratch paper, for example writing a strange string. Then he decides to have some fun rationally: count how many subsequences equal to zzy appear in this string. Note that it is subsequences rather than substrings. But the string is so long that he cannot possibly count them. So he asks you for help. Can you help him?

Input Format

One line containing a string $s$ consisting of lowercase letters.

Output Format

One line with a non-negative integer: the number of subsequences equal to zzy in the input string.

zlzhy

1

Hint

Constraints

Let $|s|$ denote the length of string $s$.

• For $70\%$ of the testdata, it is guaranteed that $|s| \le 100$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le |s| \le 10^6$, and the answer does not exceed $2^{63} - 1$.

Translated by ChatGPT 5