คุณได้รับสตริง $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$