分数: 600 点
问题陈述
对于字符串 S 由以下数字组成 1 通过 9,让 f(S) 是字符串 T 通过以下过程获得。 (S_i 表示 i- 第一个字符 S.)
- 让 T 最初是一个空字符串。
- 对于 i=1, 2, \dots, |S| - 1,执行以下操作:
- 追加 n 副本 S_i 到尾部 T,其中 n 是当 S_{i+1} 被解释为整数。
例如, S = 313 产量 f(S) = 3111 通过以下步骤。
- T 最初是空的。
- 对于 i=1,我们有 n = 1。 附加一份副本
3to T,变成3. - 对于 i=2,我们有 n = 3。 附上三份
1to T,变成3111. - 终止该过程。 我们得到 T =
3111.
给你一个长度-N 字符串 S 由以下数字组成 1 通过 9.
重复以下操作,直到长度 S 变为 1:替换 S 与 f(S).
求多少次,取模 998244353,您执行操作直至完成。 如果您要无限期地重复该操作,请打印 -1 。
约束
- 2 \leq N \leq 10^6
- S 是一个长度-N 字符串组成
1,2,3,4,5,6,7,8,和9.
输入
输入由标准输入按以下格式给出:
N S
输出
打印次数,模数 998244353,您执行操作直到完成。 如果您要无限期地重复该操作,请打印 -1 。
示例输入 1
3 313
示例输出 1
4
If S = 313,长度 S 来了 1 四次操作后。
- 我们有 f(S) =
3111。 更换 S 与3111. - 我们有 f(S) =
311。 更换 S 与311. - 我们有 f(S) =
31。 更换 S 与31. - 我们有 f(S) =
3。 更换 S 与3. - 现在的长度 S is 1,终止重复。
示例输入 2
9 123456789
示例输出 2
-1
If S = 123456789,您无限期地重复该操作。 在这种情况下, -1 。
示例输入 3
2 11
示例输出 3
1