Type: Default 1000ms 256MiB

今天的咒语有点短

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

魔法学院今天教大家念咒语:meow\texttt{meow}。

可惜同学们的键盘都比较有个性,输入出来的是一个长度为 nn 的小写字符串 ss。老师决定不为难大家:只要能从 ss 中删除若干字符,剩下的字符按原顺序正好组成 meow\texttt{meow},就算念出了一次咒语。

请问字符串 ss 中有多少个不同的子序列等于 meow\texttt{meow}?

两个子序列不同,当且仅当它们选择的下标集合不同。

答案可能很大,请对 109+710^9+7 取模。

Format

Input

第一行一个字符串 s(1≤∣s∣≤2×105)s(1 \le |s| \le 2 \times 10^5),仅由小写英文字母组成。

Output

输出一行一个整数,表示等于 meow\texttt{meow} 的子序列数量对 109+710^9+7 取模后的结果。

Samples

mmeeoow
8

Note

样例说明:可以选择两个 m\texttt{m} 中的任意一个、两个 e\texttt{e} 中的任意一个、两个 o\texttt{o} 中的任意一个,以及唯一的 w\texttt{w},共 2×2×2×1=82 \times 2 \times 2 \times 1=8 种。