A50151.蒙尘之镜

睡眼惺忪地，夏绯在回味刚刚的梦境。

梦境与一个字符串 $S = s_1 s_2 \dots s_m$ 有关。由于这个梦非常漫长，所以绯绯对其进行了一些压缩，将其表示为 $S = b_1^{a_1} b_2^{a_2} \dots b_n^{a_n}$。

绯绯称 $S$ 的子串（形如 $s_l s_{l + 1} \dots s_r$）为梦境的碎片；称一个碎片是镜像的，当且仅当其为回文串。

绯绯认为一个碎片的迷惘度为其镜像子串数；梦境的迷惘度为其所有碎片的迷惘度之和。形式化地说，梦境的迷惘度被定义为其所有子串的回文子串数之和。

现在，绯绯希望你可以求出梦境的迷惘度。由于绯绯认为得到完全精确的结果并无意义，所以你只需给出梦境迷惘度对 $998\,244\,353$ 取模后的值即可。

第一行包含一个整数 $n$，表示压缩后信息的数目。

接下来 $n$ 行，第 $i$ 行包含一个整数 $a_i$ 和一个字符 $b_i$，表示压缩后的第 $i$ 条信息。

共一行一个整数，表示梦境的迷惘度，对 $998\,244\,353$ 取模后的值。

对于样例 1，注意到任意子串皆镜像，故长为 $x$ 的碎片的迷惘度即 $\frac{x(x + 1)}{2} = \binom{x + 1}{2}$。故答案为 $\sum_{l = 1}^3 \sum_{r = l}^3 \binom{r - l + 2}{2} = 15$。

对于所有数据，保证 $1 \le n \le 10^6$，$1 \le a_i \le 10^9$，$b_i \in \{\texttt{a}, \dots, \texttt{z}\}$。

测试点编号	$n \le$	$a_i \le$	$b_i=$
1, 2	$10^2$	$1$	—
3, 4	$10^2$	$10^2$	—
5, 6	$10^2$	—	—
7, 8	$10^3$	$1$	—
9, 10	$10^3$	$10^3$	—
11, 12	$10^3$	—	—
13, 14	$10^5$	$1$	—
15, 16	$10^5$	$10^3$	—
17~19	$10^5$	$10^5$	—
20, 21	$10^5$	—	$\texttt{a}$
22~24	$10^5$	—	—
25	—	—	—