Gegeben ist eine Zeichenkette $S$ der Länge $N$, die aus den Ziffern $1, 2, \dots, 9$ besteht.
Betrachten Sie eine dreieckige Pyramide, die aus insgesamt $\frac{N(N+1)}{2}$ Blöcken besteht.
Die Pyramide ist von oben nach unten in $N$ Ebenen unterteilt, die mit $1, 2, \dots, N$ nummeriert sind. Ebene $i$ ($1 \le i \le N$) enthält $i$ Blöcke, die in einer einzigen horizontalen Reihe von links nach rechts angeordnet sind. Auf jedem Block steht eine Zeichenkette. Sei $C_{i,j}$ die Zeichenkette auf dem $j$-ten Block von links ($1 \le j \le i$) in Ebene $i$.
Die Zeichenketten $C_{i,j}$ erfüllen die folgenden Bedingungen:
- Wenn $i = N$ ist, dann ist $C_{i,j}$ die Zeichenkette der Länge $1$, die aus dem $j$-ten Zeichen von $S$ besteht.
- Wenn $1 \le i < N$ ist, dann ist $C_{i,j}$ die Verkettung von $C_{i+1,j}$ und $C_{i+1,j+1}$ in dieser Reihenfolge.
Interpretieren Sie $C_{1,1}$ als dezimale ganze Zahl und berechnen Sie ihren Wert modulo $998244353$.
Eingabe
Die Eingabe erfolgt im folgenden Format:
N S
- $N$ ist eine ganze Zahl.
- $1 \le N \le 2 \times 10^5$.
- $S$ ist eine Zeichenkette der Länge $N$, die aus den Ziffern $1, 2, \dots, 9$ besteht.
Ausgabe
Geben Sie die Antwort aus.
Beispiele
Eingabe 1
4 8192
Ausgabe 1
81191992
Eingabe 2
1 5
Ausgabe 2
5
Eingabe 3
14 11123455678999
Ausgabe 3
913063116
Hinweis
Im ersten Beispiel ist $S = 8192$. Wenn wir die Pyramide nach den Regeln aufbauen, erhalten wir $C_{1,1} = 81191992$.
Im zweiten Beispiel ist $S = 5$. Die Pyramide besteht aus einem einzigen Block, und $C_{1,1} = 5$.