נתונה לך תמורה $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]$.
אלו הם המערכים היחידים שניתן להגיע אליהם.