באלגוריתם KMP, המערך next (הידוע גם כמערך LPS, ראשי תיבות של Longest Prefix Suffix, או פונקציית הכישלון) הוא מושג מרכזי. בהינתן מחרוזת $S = s_1s_2\dots s_n$ באורך $n$, המערך next שלה $next[1..n]$ מוגדר כך ש-$next[i]$ מייצג את האורך של הרישא הממשית והסיפא הממשית השוות הארוכות ביותר של תת-המחרוזת $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