ในอัลกอริทึม KMP อาร์เรย์ next (หรือที่เรียกว่าอาร์เรย์ LPS สำหรับ Longest Prefix Suffix หรือฟังก์ชันความล้มเหลว) เป็นแนวคิดหลัก กำหนดสตริง $S = s_1s_2\dots s_n$ ที่มีความยาว $n$ อาร์เรย์ next ของมันคือ $next[1..n]$ ถูกนิยามโดยให้ $next[i]$ แทนความยาวของส่วนนำแท้ (proper prefix) และส่วนท้ายแท้ (proper suffix) ที่เหมือนกันและยาวที่สุดของสตริงย่อย $S[1..i]$ โดยเฉพาะอย่างยิ่ง $next[1] = 0$ อย่างเป็นทางการสามารถนิยามได้ดังนี้:

$$next[i] = \max_{k=0,\dots,i-1} \{k : S[1\dots k] = S[i-k+1\dots i]\}$$

ในที่นี้ $S[l..r]$ ถูกนิยามให้เป็นสตริงย่อยที่เกิดจากอักขระตัวที่ $l$ ถึงอักขระตัวที่ $r$ ของสตริง $S$ และถือว่าสำหรับ $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$ ซึ่งทั้งคู่เป็นสตริงว่าง

กำหนดอาร์เรย์ $A[1..n]$ ที่มีความยาว $n$ คุณต้องนับว่ามีสตริง $S$ ที่แตกต่างกันกี่สตริงที่มีความยาว $n$ ซึ่งนิยามบนเซตของอักขระ $\Sigma$ ที่มีอาร์เรย์ next เท่ากับอาร์เรย์ $A$ ที่กำหนดให้ทุกประการ ขนาดของเซตอักขระคือ $m$ จงแสดงผลจำนวนสตริงดังกล่าวด้วยค่ามอดูโล $998\,244\,353$

ข้อมูลนำเข้า

มีหลายชุดข้อมูลทดสอบในไฟล์เดียว บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งจำนวน $T$ ($1 \le T \le 10^5$) ซึ่งระบุจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ:

• บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n$ ($2 \le n \le 10^5$) และ $m$ ($1 \le m \le 10^6$) แทนความยาวของอาร์เรย์ที่กำหนดให้และขนาดของเซตอักขระตามลำดับ
• บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน คั่นด้วยช่องว่าง แทนอาร์เรย์ $A$ ที่กำหนดให้ รับประกันว่าสำหรับ $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$

รับประกันว่าผลรวมทั้งหมดของ $n$ ไม่เกิน $5 \times 10^5$ นั่นคือ $\sum n \le 5 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน แทนจำนวนสตริงที่สอดคล้องกับเงื่อนไข โดยหาค่าคำตอบมอดูโล $998\,244\,353$

ตัวอย่าง

ข้อมูลนำเข้า

3
3 3
0 1 2
7 3
0 0 0 1 2 3 0
7 3
0 0 0 1 2 3 1

ข้อมูลส่งออก

3
24
0

หมายเหตุ

สำหรับข้อมูลกลุ่มที่สองในตัวอย่าง สมมติให้เซตอักขระคือ $\Sigma = \{'a', 'b', 'c'\}$ สตริงทั้ง $24$ ตัวที่ตรงตามข้อกำหนดได้แก่:

abbabbb abbabbc abcabcb abcabcc acbacbb acbacbc
accaccb accaccc baabaaa baabaac bacbaca bacbacc
bcabcaa bcabcac bccbcca bccbccc caacaaa caacaab
cabcaba cabcabb cbacbaa cbacbab cbbcbba cbbcbbb