103134: [Atcoder]ABC313 E - Duplicate

Problem Statement

For a string $S$ consisting of digits from 1 through 9, let $f(S)$ be the string $T$ obtained by the following procedure. ($S_i$ denotes the $i$-th character of $S$.)

• Let $T$ be an initially empty string.
• For $i=1, 2, \dots, |S| - 1$, perform the following operation:
  • Append $n$ copies of $S_i$ to the tail of $T$, where $n$ is the value when $S_{i+1}$ is interpreted as an integer.

For example, $S =$ 313 yields $f(S) =$ 3111 by the following steps.

• $T$ is initially empty.
• For $i=1$, we have $n = 1$. Append one copy of 3 to $T$, which becomes 3.
• For $i=2$, we have $n = 3$. Append three copies of 1 to $T$, which becomes 3111.
• Terminate the procedure. We obtain $T =$ 3111.

You are given a length-$N$ string $S$ consisting of digits from 1 through 9.
You repeat the following operation until the length of $S$ becomes $1$: replace $S$ with $f(S)$.
Find how many times, modulo $998244353$, you perform the operation until you complete it. If you will repeat the operation indefinitely, print -1 instead.

Constraints

• $2 \leq N \leq 10^6$
• $S$ is a length-$N$ string consisting of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Input

The input is given from Standard Input in the following format:

$N$
$S$

Output

Print the number of times, modulo $998244353$, that you perform the operation until you complete it. If you will repeat the operation indefinitely, print -1 instead.

Sample Input 1

3
313

Sample Output 1

4

If $S =$ 313, the length of $S$ be comes $1$ after four operations.

• We have $f(S) =$ 3111. Replace $S$ with 3111.
• We have $f(S) =$ 311. Replace $S$ with 311.
• We have $f(S) =$ 31. Replace $S$ with 31.
• We have $f(S) =$ 3. Replace $S$ with 3.
• Now that the length of $S$ is $1$, terminate the repetition.

Sample Input 2

9
123456789

Sample Output 2

-1

If $S =$ 123456789, you indefinitely repeat the operation. In this case, -1 should be printed.

Sample Input 3

2
11

Sample Output 3

1

问题描述

对于由数字1到9组成的字符串$S$，定义$f(S)$为通过以下过程得到的字符串$T$。（$S_i$表示$S$的第$i$个字符。）

• 将$T$初始化为空字符串。
• 对于$i=1, 2, \dots, |S| - 1$，执行以下操作：
  • 在$T$的尾部添加$S_i$的$n$个副本，其中$n$为将$S_{i+1}$解释为整数时的值。

例如，对于$S =$ 313，通过以下步骤得到$f(S) =$ 3111。

• $T$最初为空。
• 对于$i=1$，我们有$n = 1$。在$T$的尾部添加一个3的副本，$T$变为3。
• 对于$i=2$，我们有$n = 3$。在$T$的尾部添加三个1的副本，$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

如果$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$的长度为$1$，终止重复。

样例输入2

9
123456789

样例输出2

-1

如果$S =$ 123456789，你会无限期地重复此操作。在这种情况下，应该打印-1。

样例输入3

2
11

样例输出3

1