給你一個長度為 $N$ 且僅由數字 $1, 2, \dots, 9$ 組成的字串 $S$。
考慮一個由總共 $\frac{N(N+1)}{2}$ 個方塊組成的三角金字塔。
該金字塔自頂向下分為 $N$ 層,編號為 $1, 2, \dots, N$。第 $i$ 層($1 \le i \le N$)包含 $i$ 個方塊,由左至右排成一橫排。每個方塊上都寫有一個字串。記 $C_{i,j}$ 為第 $i$ 層中由左至右數第 $j$ 個方塊($1 \le j \le i$)上寫的字串。
字串 $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$ 是一個長度為 $N$ 且僅由數字 $1, 2, \dots, 9$ 組成的字串。
輸出格式
輸出答案。
範例
輸入範例 1
4 8192
輸出範例 1
81191992
輸入範例 2
1 5
輸出範例 2
5
輸入範例 3
14 11123455678999
輸出範例 3
913063116
說明
在第一個範例中,$S = 8192$。根據規則構建金字塔,我們得到 $C_{1,1} = 81191992$。
在第二個範例中,$S = 5$。金字塔僅由一個方塊組成,且 $C_{1,1} = 5$。