题目描述

约定 $S_i$ 为字符串 $S$ 的左起第 $i$ 个字符，$|S|$ 为字符串 $S$ 的长度。

对于一个由数字字符 1 到 9 组成的字符串 $S$，定义 $f(S)$ 为根据以下流程生成的字符串 $T$:

• $T$ 一开始是空字符串；
• 对于 $i=1,2,3,\cdots,|S|-1$，将 $S_i$ 加到 $T$ 的末尾 $n$ 次，其中 $n$ 是 $S_{i+1}$ 表示的数。

比如，$S=$ 313 时，如下步骤得到 $f(S)=$ 3111：

• $T$ 一开始是空字符串；
• 对于 $i=1$，有 $n=1$，将 3 加到 $T$ 的末尾 $1$ 次，此时 $T=$ 3；
• 对于 $i=2$，有 $n=3$，将 1 加到 $T$ 的末尾 $3$ 次，此时 $T=$ 3111；
• $f(S)=T=$ 3111；

输入一个长度为 $n$ 的，由数字字符 1 到 9 组成的字符串 $S$。

现在不断地用 $f(S)$ 替换 $S$，直到 $|S|=1$，输出进行的替换次数对 $998244353$ 取模的值。若无法在有限次替换内使得 $|S|=1$，输出 -1。

例如输入 $n=3$，$S=$ 313，需要进行如下 $4$ 次替换：

$\texttt{313} \to \texttt{3111} \to \texttt{311} \to \texttt{31} \to \texttt{3}$

所以输出 4。

输入格式

第一行一个整数 $n$，$2 \leq n \leq 10^6$。

第二行一个长度为 $n$ 的字符串 $S$。

输出格式

一个整数表示答案。

3
313

4

9
123456789

-1

2
11

1