Bạn được cho một xâu $S$ độ dài $N$ gồm các chữ số $1, 2, \dots, 9$.
Xét một kim tự tháp tam giác được tạo thành từ tổng cộng $\frac{N(N+1)}{2}$ khối.
Kim tự tháp được chia thành $N$ tầng, được đánh số $1, 2, \dots, N$ từ trên xuống dưới. Tầng $i$ ($1 \le i \le N$) chứa $i$ khối được xếp thành một hàng ngang duy nhất từ trái sang phải. Mỗi khối có ghi một xâu. Gọi $C_{i,j}$ là xâu được ghi trên khối thứ $j$ tính từ bên trái ($1 \le j \le i$) ở tầng $i$.
Các xâu $C_{i,j}$ thỏa mãn các điều kiện sau:
- Nếu $i = N$, thì $C_{i,j}$ là xâu độ dài $1$ gồm ký tự thứ $j$ của $S$.
- Nếu $1 \le i < N$, thì $C_{i,j}$ là xâu ghép của $C_{i+1,j}$ và $C_{i+1,j+1}$, theo đúng thứ tự này.
Hãy coi $C_{1,1}$ như một số nguyên hệ thập phân và tính giá trị của nó theo modulo $998244353$.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
N S
- $N$ là một số nguyên.
- $1 \le N \le 2 \times 10^5$.
- $S$ là một xâu độ dài $N$ gồm các chữ số $1, 2, \dots, 9$.
Dữ liệu ra
In ra đáp án.
Ví dụ
Dữ liệu vào 1
4 8192
Dữ liệu ra 1
81191992
Dữ liệu vào 2
1 5
Dữ liệu ra 2
5
Dữ liệu vào 3
14 11123455678999
Dữ liệu ra 3
913063116
Ghi chú
Trong ví dụ đầu tiên, $S = 8192$. Bằng cách xây dựng kim tự tháp theo quy tắc, ta thu được $C_{1,1} = 81191992$.
Trong ví dụ thứ hai, $S = 5$. Kim tự tháp chỉ gồm một khối duy nhất và $C_{1,1} = 5$.