E - Duplicate Editorial /

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 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