题目描述

gshfd1jkhaRaadfglkjerVcvuy0gf said Prof. Pang.

To understand Prof. Pang's word, we would like to calculate the number of $\textit{namomo subsequence}$s of it. The word by Prof. Pang is a string $s$ with $n$ characters where each character is either an English letter (lower or upper case) or a digit. The $i$-th character of $s$ is denoted by $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]$ represents 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$.

输入格式

The first line contains a string $s$ with $n$ characters ($6\le n\le 1000000$). $s$ contains only lower case English letters (a -- z), upper case English letters (A -- Z) and digits (0 -- 9).

输出格式

Output one integer -- the answer modulo $998244353$.

题目大意

题目描述

庞教授说：“gshfd1jkhaRaadfglkjerVcvuy0gf 。”

为了理解庞教授的话，我们需要计算字符串中的 $\textit{namomo 子序列}$ 的数量。庞教授的话是一个包含 $n$ 个字符的字符串 $s$，其中每个字符要么是英文字母（大小写皆可），要么是数字。字符串 $s$ 的第 $i$ 个字符表示为 $s[i]$（$1\le i\le n$）。一个 $s$ 的子序列 $t$ 是由一系列索引 $t_1, \ldots, t_6$ 定义的，其中 $1\le t_1 < t_2 < \ldots < t_6\le n$。设 $compare(c_1, c_2)$ 是一个函数，其对两个字符的比较定义为：当 $c_1=c_2$ 时，$compare(c_1, c_2)=1$，否则 $compare(c_1, c_2)=0$。当且仅当对于任意的 $1\le i<j\le 6$，都有 $compare(s[t_i], s[t_j]) = compare(namomo[i], namomo[j])$ 时，$t$ 是 $s$ 的一个 namomo 子序列，其中 $namomo[x]$ 表示字符串 "namomo" 的第 $x$ 个字符 ($1\le x\le 6$)。

输出给定字符串 $s$ 的 namomo 子序列的数量，结果对 $998244353$ 取模。

输入格式

第一行包含一个字符串 $s$，长度为 $n$ ($6\le n\le 1000000$)。字符串 $s$ 仅包含小写字母（a -- z）、大写字母（A -- Z）以及数字（0 -- 9）。

输出格式

输出一个整数——结果对 $998244353$ 取模。

翻译者：Immunoglobules

wohaha

1

momomo

0

gshfd1jkhaRaadfglkjerVcvuy0gf

73

retiredMiFaFa0v0

33