Score : $600$ points

问题描述

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

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

例如，当 $S=$ 313 时，按照以下步骤可得 $f(S)=$ 3111。

• $T$ 初始为空。
• 当 $i=1$ 时，我们有 $n = 1$。向 $T$ 追加一个 3 的副本，使其变为 3。
• 当 $i=2$ 时，我们有 $n = 3$。向 $T$ 追加三个 1 的副本，使其变为 3111。
• 结束该过程。我们得到 $T=$ 3111。

给定一个长度为 $N$、由数字1至9组成的字符串 $S$。

您需要重复以下操作，直到字符串 $S$ 的长度变为 $1$：用 $f(S)$ 替换 $S$。

求出在完成操作之前，你需要进行此操作的次数，并对 $998244353$ 取模。如果该操作会无限重复，请输出 -1。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:56:04