E. Симон и деление ритма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

I grip my troubles within my hand, then hurl them off a thousand lands.
— SHUN, ONMYWAY

Симону дан массив $$$a$$$ размером $$$m$$$.

Симон должен ровно один раз выполнить над массивом следующую операцию:

  • Сначала он должен выбрать целое число $$$k$$$ и выбрать $$$k$$$ пар целых чисел $$$[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$$$, такие что:
    • $$$l_i\le r_i$$$ для каждого $$$1\le i\le k$$$,
    • $$$l_1=1$$$, $$$r_k=m$$$, и
    • $$$r_i+1=l_{i+1}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$k-1$$$.
  • Затем он независимо разворачивает каждый подотрезок $$$[a_{l_i},a_{l_i+1},\ldots, a_{r_i}]$$$. После этого массив станет $$$[a_{r_1},a_{r_1-1},\ldots,a_{l_1},a_{r_2},\ldots,a_{l_{k-1}},a_{r_{k}},a_{r_k-1},\ldots,a_{l_k}]$$$.

Вам дан массив $$$T$$$ размером $$$n$$$. Подсчитайте количество массивов $$$S$$$, таких что Симон может преобразовать $$$S$$$ в $$$T$$$, по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 8000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит целое число $$$n$$$ ($$$1\le n\le 8000$$$) — размер массива $$$T$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$T_1,T_2,\ldots,T_n$$$ ($$$1\le T_i\le 8000$$$) — элементы массива $$$T$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$8000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество массивов $$$S$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
4
1 1 2 1
4
1 2 3 1
6
1 3 2 3 3 2
10
2 3 1 4 3 1 4 3 1 2
1
8000
Выходные данные
4
7
22
383
1
Примечание

В первом наборе входных данных только следующие массивы могут быть преобразованы в $$$T$$$:

  • Для $$$S=[2,1,1,1]$$$, Симон выберет $$$[1,3]$$$ и $$$[4,4]$$$. Таким образом, массив станет $$$[1,1,2,1]$$$, равным $$$T$$$.
  • Для $$$S=[1,2,1,1]$$$, Симон выберет $$$[1,4]$$$.
  • Для $$$S=[1,1,2,1]$$$, Симон выберет $$$[1,2]$$$, $$$[3,3]$$$ и $$$[4,4]$$$.
  • Для $$$S=[1,1,1,2]$$$, Симон выберет $$$[1,2]$$$ и $$$[3,4]$$$.

Во втором наборе входных данных только следующие массивы могут быть преобразованы в $$$T$$$:

  • Для $$$S=[1,1,3,2]$$$, Симон выберет $$$[1,1]$$$ и $$$[2,4]$$$.
  • Для $$$S=[1,2,1,3]$$$, Симон выберет $$$[1,1]$$$, $$$[2,2]$$$ и $$$[3,4]$$$.
  • Для $$$S=[1,2,3,1]$$$, Симон выберет $$$[1,1]$$$, $$$[2,2]$$$, $$$[3,3]$$$ и $$$[4,4]$$$.
  • Для $$$S=[1,3,2,1]$$$, Симон выберет $$$[1,4]$$$.
  • Для $$$S=[2,1,1,3]$$$, Симон выберет $$$[1,2]$$$ и $$$[3,4]$$$.
  • Для $$$S=[2,1,3,1]$$$, Симон выберет $$$[1,2]$$$, $$$[3,3]$$$ и $$$[4,4]$$$.
  • Для $$$S=[3,2,1,1]$$$, Симон выберет $$$[1,3]$$$ и $$$[4,4]$$$.