数字 $1, 2, \dots, 9$ からなる長さ $N$ の文字列 $S$ が与えられます。
合計 $\frac{N(N+1)}{2}$ 個のブロックからなる三角形のピラミッドを考えます。
ピラミッドは上から下へ $1, 2, \dots, N$ と番号付けられた $N$ 個の層に分かれています。第 $i$ 層($1 \le i \le N$)には、左から右へ水平に一列に並んだ $i$ 個のブロックが含まれています。各ブロックには文字列が書かれています。第 $i$ 層の左から $j$ 番目($1 \le j \le i$)のブロックに書かれた文字列を $C_{i,j}$ と表します。
文字列 $C_{i,j}$ は以下の条件を満たします:
- $i = N$ のとき、$C_{i,j}$ は $S$ の $j$ 番目の文字からなる長さ $1$ の文字列である。
- $1 \le i < N$ のとき、$C_{i,j}$ は $C_{i+1,j}$ と $C_{i+1,j+1}$ をこの順に連結した文字列である。
$C_{1,1}$ を十進法の整数とみなしたときの値を $998244353$ で割った余りを求めてください。
入力
入力は以下の形式で与えられます:
N S
- $N$ は整数である。
- $1 \le N \le 2 \times 10^5$。
- $S$ は数字 $1, 2, \dots, 9$ からなる長さ $N$ の文字列である。
出力
答えを出力してください。
入出力例
入力例 1
4 8192
出力例 1
81191992
入力例 2
1 5
出力例 2
5
入力例 3
14 11123455678999
出力例 3
913063116
ノート
最初の例では、$S = 8192$ です。規則に従ってピラミッドを構築すると、$C_{1,1} = 81191992$ が得られます。
2 番目の例では、$S = 5$ です。ピラミッドは 1 つのブロックのみからなり、$C_{1,1} = 5$ です。