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.

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.

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.

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

见题面 Input 部分

见题面 Output 部分