Namomo Subsequence

Time limit3sMemory limit1024 MB

Summary

Count the length-6 subsequences of s whose equal-character pattern matches

Level: Medium5 of 10
Topics: String, Dynamic programming, Hash map
Solved: No attempts yet

Problem

"gshfd1jkhaRaadfglkjerVcvuy0gf" said Prof. Pang.

To understand Prof. Pang's word, we would like to calculate the number of namomo subsequences of it. The word by Prof. Pang is a string $s$ with $n$ characters, where each character is either an English letter (lowercase or uppercase) or a digit. The $i$ -th character of $s$ is denoted $s[i]$ ( $1 \le i \le n$ ). A subsequence $t$ of $s$ is defined by a list of indices $t_1, \ldots, t_6$ such that $1 \le t_1 < t_2 < \ldots < t_6 \le n$ . Let $compare(c_1, c_2)$ be a function on two characters such that $compare(c_1, c_2) = 1$ when $c_1 = c_2$ and $compare(c_1, c_2) = 0$ otherwise. $t$ is a namomo subsequence of $s$ if and only if for any $1 \le i < j \le 6$ , $compare(s[t_i], s[t_j]) = compare(namomo[i], namomo[j])$ , where $namomo[x]$ is the $x$ -th character of the string "namomo" ( $1 \le x \le 6$ ).

Output the number of namomo subsequences of a given string $s$ modulo $998244353$ .

Input

The first line contains a string $s$ with $n$ characters ( $6 \le n \le 1000000$ ). $s$ contains only lowercase English letters ('a' to 'z'), uppercase English letters ('A' to 'Z'), and digits ('0' to '9').

Output

Output one integer, the answer modulo $998244353$ .

Examples4

Example 1
Input
```
wohaha
```
Expected output
```
1
```
Example 2
Input
```
momomo
```
Expected output
```
0
```
Example 3
Input
```
gshfd1jkhaRaadfglkjerVcvuy0gf
```
Expected output
```
73
```
Example 4
Input
```
retiredMiFaFa0v0
```
Expected output
```
33
```