#1504. [L3-2] 超级恶臭字符串

若两个字符串 $S=s_1s_2\cdots s_n$ 和 $T=t_1t_2\cdots t_m$ 完全相同，即 $n=m$，且对于任意的 $1\le i\le n$ 都有 $s_i=t_i$，则我们记 $S=T$. 否则，我们记 $S\not= T$.

若有两个字符串 $S=s_1s_2\cdots s_n$ 和 $T=t_1t_2\cdots t_m$，我们记这两个字符的拼接为 $S+T=s_1s_2\cdots s_n t_1t_2\cdots t_m$.

若有一个字符串 $S=s_1s_2\cdots s_n$，我们记其子串 $S[l,r]=s_{l}s_{l+1}\cdots s_r$.

我们称一个字符串 $S$ 的恶臭程度为 $f(S)$，表示将 $S$ 分割 $7$ 个字符串 $S_1,S_2,\cdots,S_7$，且这 $7$ 个字符串满足如下性质的方案数：

• $S=S_1+S_2+\cdots +S_7$.

• $S_1=S_3=S_6$.

• $S_2=S_4$.

• $S_1,S_2,\cdots S_7$ 不能为空串.

对于两个分割 $S_1,S_2,\cdots S_7$ 和 $S'_1,S'_2,\cdots,S'_7$，只要存在一个 $i$（$1\le i\le 7$）使得 $S_i\not= S'_i$，则视为两个不同的分割方案.

例如，$\texttt{1919810}$ 就是一个恶臭程度为 $1$ 的字符串，因为其可以分割为 $S_1=\texttt{1}$，$S_2=\texttt{9}$，$S_3=\texttt{1}$，$S_4=\texttt{9}$，$S_5=\texttt{8}$，$S_6=\texttt{1}$，$S_7=\texttt{0}$，满足之前所述的条件，并且不存在其他分割方式.

定义一个长度为 $n$ 的字符串 $S$ 的超级恶臭程度 $g(S)$，为 $S$ 的所有子串的恶臭程度之和. 即：

$$g(S)=\sum_{l=1}^n\sum_{r=l}^n f(S[l,r])$$

给定一个字符串 $S$，求其超级恶臭程度 $g(S)$，对 998244353 取模的结果.

第一行包含一个正整数 $n$，表示字符串 $S$ 的长度.

第二行包含一个字符串 $S$. 保证 $S$ 仅由数字 $\texttt{0}\sim \texttt{9}$ 构成.

输出一行，包含一个整数，表示 $g(S)$ 的超级恶臭程度，对 998244353 取模的结果.

输入样例 1

7
1919810

输出样例 1

1

输入样例 2

11
11011011110

输出样例 2

12

$7\le n\le 5000$

保证字符串 $S$ 仅由数字 $\texttt{0}\sim \texttt{9}$ 构成.