تُعطى تبديلاً $P$ للمجموعة $\{1, 2, \dots, N\}$.
أي أن $P$ هي مصفوفة بطول $N$ تحتوي على كل عدد صحيح من $1$ إلى $N$ مرة واحدة بالضبط.
يمكنك إجراء العملية التالية عليها:
- اختر فهرسًا $i$ ($1 < i < |P|$).
- عيّن $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- احذف $P_{i-1}$ و $P_{i+1}$ من $P$. ثم تتم إعادة فهرسة العناصر المتبقية لتبدأ من $1$.
كل عملية من هذا القبيل تقلل طول $P$ بمقدار $2$. وعلى وجه الخصوص، إذا كان طول $P$ هو $1$ أو $2$، فلا يمكن تطبيق هذه العملية.
أوجد عدد المصفوفات المختلفة التي يمكن الوصول إليها عن طريق إجراء هذه العملية صفرًا أو أكثر من المرات بدءًا من $P$.
بما أن هذه القيمة قد تكون كبيرة، فإنك تحتاج فقط إلى إيجادها بباقي القسمة على $998\,244\,353$.
الإدخال
يُعطى الإدخال بالصيغة التالية:
T N P_1 P_2 ... P_N ...
القيود
- جميع قيم الإدخال هي أعداد صحيحة.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ لكل $i \ne j$.
- من المضمون أن مجموع $N^2$ عبر جميع حالات الاختبار لا يتجاوز $5000^2$.
الإخراج
لكل حالة اختبار، اطبع عددًا صحيحًا واحدًا — عدد المصفوفات المختلفة التي يمكن الوصول إليها عن طريق إجراء العملية صفرًا أو أكثر من المرات على $P$، بباقي القسمة على $998\,244\,353$.
مثال
الإدخال 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
الإخراج 1
1 2 5 55 365
ملاحظة
حالة الاختبار 1: لا يمكن إجراء أي عمليات.
حالة الاختبار 2: هناك احتمالان:
- عدم إجراء أي عمليات. المصفوفة النهائية هي $[2, 1, 3]$.
- إجراء عملية واحدة مع $i = 2$. المصفوفة النهائية هي $[3]$.
هذه هي المصفوفات الوحيدة التي يمكن الوصول إليها.