P2646 Counting zzy

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?

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

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

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