回想一下,如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。例如,对于字符串 $$$a$$$="wowwo",以下字符串是子序列:"wowwo"、"wowo"、"oo"、"wow"、"" 等,但以下字符串不是子序列:"owoo"、"owwo"、"ooo"。
字符串的 wow 因子是其等于单词“wow”的子序列的数量。鲍勃想要编写一个具有很大令人惊叹因素的字符串。然而,他键盘上的“w”键坏了,所以他输入了两个“v”。
他几乎没有意识到他引入的“w”可能比他想象的要多。例如考虑字符串“ww”。 Bob 会将其键入为“vvvv”,但该字符串实际上包含三个“w”:
- “vvvv”
- “vvvv”
- “vvvv”
例如,单词“vvvovvv”的哇因子等于 4,因为有四个哇:
- “vvvovvv”
- “vvvovvv”
- “vvvovvv”
- “vvvovvv”
请注意,子序列“vvvovvv”不计入令人惊叹的因素,因为“v”必须是连续的。
对于给定的字符串 $$$s$$$,计算并输出其 wow 因子。请注意,不保证可以从另一个用“vv”替换“w”的字符串中获取$$$s$$$。例如,$$$s$$$ 可以等于“vov”。
输入
输入包含单个非空字符串 $$$s$$$,仅包含字符“v”和“o”。 $$$s$$$ 的长度最多为 $$$10^6$$$。
输出
输出一个整数,$$$s$$$ 的 wow 因子。
示例
输入 #1
vvvovvv
输出 #1
4
输入 #2
vvovooovovvovoovoovvvvovovvvov
输出 #2
100
注意
第一个示例在图例中进行了解释。