Сізге $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$ аламыз.
Екінші мысалда $S = 5$. Пирамида бір ғана блоктан тұрады және $C_{1,1} = 5$.