Сізге $\{1, 2, \dots, N\}$ жиынының $P$ орын алмастыруы берілген.
Яғни, $P$ — $1$-ден $N$-ге дейінгі әрбір бүтін санды дәл бір рет қамтитын ұзындығы $N$ болатын массив.
Оған келесі операцияны қолдануға болады:
- $i$ ($1 < i < |P|$) индексін таңдаңыз.
- $P_i = \max(P_{i-1}, P_i, P_{i+1})$ деп орнатыңыз.
- $P$ массивінен $P_{i-1}$ және $P_{i+1}$ элементтерін өшіріңіз. Қалған элементтер $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$
- Барлық $i \ne j$ үшін $P_i \ne P_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]$.
Қол жеткізуге болатын массивтер тек осылар.