重复

题目描述

对于由 1 到 9 的数字组成的字符串 $S$,令 $f(S)$ 为按以下步骤得到的字符串 $T$。($S_i$ 表示 $S$ 的第 $i$ 个字符。)

• 令 $T$ 为空字符串。
• 按 $i=1, 2, \dots, |S| - 1$ 的顺序执行以下操作:将 $S_{i+1}$ 解释为整数时的值记为 $n$,向 $T$ 的末尾追加 $n$ 个 $S_i$。

例如,当 $S =$ 313 时,通过以下步骤得到 $f(S) =$ 3111:

• 起初 $T$ 为空字符串。
• 当 $i=1$ 时,$n=1$。向 $T$ 追加 1 个 3,$T$ 变为 3。
• 当 $i=2$ 时,$n=3$。向 $T$ 追加 3 个 1,$T$ 变为 3111。
• 操作结束,得到 $T =$ 3111。

给定一个由 1 到 9 的数字组成、长度为 $N$ 的字符串 $S$。 你重复执行「将 $S$ 替换为 $f(S)$」这一操作,直到 $S$ 的长度变为 1。 求操作结束之前执行操作的总次数对 $998244353$ 取模的结果。如果操作会无限持续下去,则输出 $-1$。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$

输出格式

输出操作结束之前执行操作的总次数对 $998244353$ 取模的结果。如果操作会无限持续下去,则输出 $-1$。

样例

3
313

4

当 $S =$ 313 时,经过 4 次操作,$S$ 的长度变为 1:

• $f(S) =$ 3111,将 $S$ 替换为 3111。
• $f(S) =$ 311,将 $S$ 替换为 311。
• $f(S) =$ 31,将 $S$ 替换为 31。
• $f(S) =$ 3,将 $S$ 替换为 3。

现在 $S$ 的长度为 1,操作结束。

9
123456789

-1

当 $S =$ 123456789 时,操作会无限持续下去。此时应输出 $-1$。

2
11

1

数据范围

• $2 \le N \le 10^6$
• $S$ 是由 1、2、3、4、5、6、7、8、9 组成的长度为 $N$ 的字符串