Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1
から 9
までの数字からなる文字列 S に対して、 f(S) を次の手順によって得られる文字列 T とします。(S_i は S の i 番目の文字を意味します)
- 文字列 T がある。はじめ、T は空文字列である。
- i=1, 2, \dots, |S| - 1 の順に次の操作を行う。
- S_{i+1} を整数として解釈したときの値を n とする。T の末尾に S_i を n 個追加する。
例えば S = 313
のとき、以下の手順によって f(S) = 3111
に決まります。
- はじめ T は空文字列である。
- i=1 のとき n = 1 である。T に
3
を 1 個追加する。T は3
になる。 - i=2 のとき n = 3 である。T に
1
を 3 個追加する。T は3111
になる。 - 操作を終了する。T として
3111
を得る。
1
から 9
までの数字からなる長さ N の文字列 S が与えられます。
あなたは「S を f(S) に置き換える」という操作を S の長さが 1 になるまで繰り返します。
操作が終了するまでに行う操作を行う回数を 998244353 で割った余りを求めてください。ただし、操作が無限に続く場合は -1
を出力してください。
制約
- 2 \leq N \leq 10^6
- S は
1
,2
,3
,4
,5
,6
,7
,8
,9
からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
操作が終了するまでに行う操作を行う回数を 998244353 で割った余りを出力せよ。ただし、操作が無限に続く場合は -1
を出力せよ。
入力例 1
3 313
出力例 1
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 になったので操作を終了する。
入力例 2
9 123456789
出力例 2
-1
S = 123456789
の場合、操作が無限に続きます。この場合は -1
を出力してください。
入力例 3
2 11
出力例 3
1
Score : 600 points
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 becomes3
. - For i=2, we have n = 3. Append three copies of
1
to T, which becomes3111
. - 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
, and9
.
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 with3111
. - We have f(S) =
311
. Replace S with311
. - We have f(S) =
31
. Replace S with31
. - We have f(S) =
3
. Replace S with3
. - 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