נתונה לכם מחרוזת $S$ באורך $N$ המורכבת מהספרות $1, 2, \dots, 9$.
נתבונן בפירמידה משולשת המורכבת מסך הכל $\frac{N(N+1)}{2}$ בלוקים.
הפירמידה מחולקת ל-$N$ שכבות, הממוספרות $1, 2, \dots, N$ מלמעלה למטה. שכבה $i$ ($1 \le i \le N$) מכילה $i$ בלוקים המסודרים בשורה אופקית אחת משמאל לימין. על כל בלוק כתובה מחרוזת. נסמן ב-$C_{i,j}$ את המחרוזת הכתובה על הבלוק ה-$j$ משמאל ($1 \le j \le i$) בשכבה $i$.
המחרוזות $C_{i,j}$ מקיימות את התנאים הבאים:
- אם $i = N$, אזי $C_{i,j}$ היא המחרוזת באורך $1$ המורכבת מהתו ה-$j$ של $S$.
- אם $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$.