Background

Special for beginners, ^_^

Description

有一个 $N（1<N\le10^6）$ 位的仅含有数字 1~ 9 的数字串，串的相邻两位，从左到右分别记为 $a$ 和 $b$ ，可以看作是一个行程编码，即数字 $a$ 重复了 $b$ 次，解码之。

举个例子： 初始的字符串为313，则按照一下过程解码： 313 -> 3111 -> 311 -> 31 -> 3。 经过 4 次解码，最终得到了 1 个一位数。

那么问题来了，给出一个 $N（1<N\le10^6）$ 位的数字串 $S$ ，问能否通过有限次解码操作得到一个一位数。

如果可以，则输出操作次数 （mod 998244353）。

如果不行，则输出 -1 。

Format

Input

输入两行，第一行是一个整数 $N$，第二行是一个长度为 $N$ 的数字串 $S$ 。

Output

在一行中输出答案。.

Samples

3
313

4

Limitation

1s, 1024KiB for each test case.