Namomo Subsequences

Professor Pang once said, "gshfd1jkhaRaadfglkjerVcvuy0gf". In order to understand his mysterious words, we need to count the number of namomo subsequences of the given string.

We are given a string (s) of length (n) where each character is either an English letter (lowercase or uppercase) or a digit. The (i)th character is denoted by (s[i]) ((1 \le i \le n)). A subsequence (t) of (s) is defined by a list of indices (t_1, t_2, \ldots, t_6) (with (1 \le t_1 < t_2 < \cdots < t_6 \le n)).

Let (compare(c_1, c_2)) be defined as [ compare(c_1, c_2)=\begin{cases}1,&\text{if } c_1=c_2,\0,&\text{otherwise.}\end{cases} ]

The string “namomo” has 6 characters: (n, a, m, o, m, o). A 6-tuple (t) is a namomo subsequence of (s) if and only if for every (1 \le i < j \le 6): [ compare(s[t_i], s[t_j]) = compare(\mathtt{namomo}[i],,\mathtt{namomo}[j]). ]

In other words, if we label the positions as follows:

• Position 1 corresponds to a new letter (call it (X_1)).
• Position 2 corresponds to a different new letter ((X_2), with (X_2\neq X_1)).
• Position 3 corresponds to a new letter ((X_3)), and position 5 must be the same as position 3 (i.e. (X_3)).
• Position 4 corresponds to a new letter ((X_4)), and position 6 must be the same as position 4 (i.e. (X_4)).

Also, all letters that are meant to be different (i.e. (X_1, X_2, X_3, X_4)) must be pairwise distinct and additionally (X_3 \neq X_4).

Moreover, the indices chosen must satisfy [ t_1 < t_2 < t_3 < t_4 < t_5 < t_6. ]

Your task is to output the number of namomo subsequences of (s) modulo (998244353).

Explanation

For a valid subsequence, assume we choose letters \(X_1, X_2, X_3, X_4\) from \(s\) for positions 1,2,3,4 respectively. Then positions 5 and 6 must use the same letters as positions 3 and 4 respectively. The indices picked from \(s\) for these letters must appear in increasing order and obey the additional ordering constraints:

1. Choosing an index from the occurrences of \(X_1\) for position 1.
2. Choosing an index from the occurrences of \(X_2\) for position 2 such that it comes after the one chosen for \(X_1\).
3. Choosing two indices (in order) from the occurrences of \(X_3\) for positions 3 and 5, which must come after the index picked for \(X_2\), with the first chosen before the second.
4. Choosing two indices (in order) from the occurrences of \(X_4\) for positions 4 and 6 such that the first is after the index chosen for position 3 and before the second index chosen for \(X_3\), and the second occurs after the second occurrence of \(X_3\).

You must count the total number of valid choices modulo 998244353.

inputFormat

The input consists of a single line containing the string (s).

outputFormat

Output a single integer, the number of namomo subsequences modulo (998244353).

sample

namomo

1