KMP алгоритмінде next массиві (сондай-ақ LPS массиві — Longest Prefix Suffix — немесе префикс-функция ретінде белгілі) негізгі ұғым болып табылады. Ұзындығы $n$ болатын $S = s_1s_2\dots s_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]$ дегеніміз $S$ жолының $l$-ші таңбасынан $r$-ші таңбасына дейінгі таңбалардан құралған ішкі жол. $\forall 1 \le i \le n$ үшін $S[1\dots 0] = S[i+1\dots i]$ деп есептеледі, олардың екеуі де бос жолдар.

Ұзындығы $n$ болатын $A[1..n]$ массиві берілген. $\Sigma$ таңбалар жиынында анықталған, ұзындығы $n$ болатын әртүрлі $S$ жолдарының ішінде 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$) берілген.
• Екінші жолда бос орындармен бөлінген, берілген $A$ массивін сипаттайтын $n$ бүтін сан берілген. $\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