في خوارزمية 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