← 返回题目列表

AtCoder · abc313_e

H. 重复

中文机器翻译题面 查看原题

分数: 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。 附加一份副本 3 to T,变成 3.
  • 对于 i=2,我们有 n = 3。 附上三份 1 to 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