CF2205E.Simons and Dividing the Rhythm

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

— SHUN, ONMYWAY

Consider that Simons is given an array $a$ of size $m$.

Simons must operate on the array exactly once as follows:

• First, he has to select an integer $k$ and choose $k$ pairs of integers $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$, such that:
  • $l_i\le r_i$ for each $1\le i\le k$,
  • $l_1=1$, $r_k=m$, and
  • $r_i+1=l_{i+1}$ for each $i$ from $1$ to $k-1$.
• Then, he reverses each subarray $[a_{l_i},a_{l_i+1},\ldots, a_{r_i}]$ independently. After this, the array will become $[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}]$.

You are given an array $T$ of size $n$. Count the number of arrays $S$ such that Simons can transform $S$ to $T$, modulo $998\,244\,353$.

我将烦恼紧握于掌中，然后将其掷向千里之外。

—— SHUN，《ONMYWAY》Spotify 链接

考虑 Simons 被给定一个长度为 $m$ 的数组 $a$。

Simons 必须对这个数组恰好执行一次如下操作：

• 首先，他需选定一个整数 $k$，并选择 $k$ 对整数 $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$，满足：
  • 对每个 $1\le i\le k$，有 $l_i\le r_i$；
  • $l_1=1$，$r_k=m$；
  • 对每个 $i = 1$ 到 $k-1$，有 $r_i+1=l_{i+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}]$。

现给定一个长度为 $n$ 的数组 $T$。请计算满足“Simons 可将数组 $S$ 经上述操作变换为 $T$”的数组 $S$ 的个数，结果对 $998\,244\,353$ 取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 8000$). The description of the test cases follows.

The first line contains an integer $n$ ($1\le n\le 8000$) — the length of $T$.

The second line contains $n$ integers $T_1,T_2,\ldots,T_n$ ($1\le T_i\le 8000$) — the elements of $T$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $8000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the number of arrays $S$, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——满足条件的数组 $S$ 的个数，对 $998\,244\,353$ 取模。

In the first test case, we can see only the following arrays can be transformed to $T$:

• For $S=[2,1,1,1]$, Simons will choose $[1,3]$ and $[4,4]$. Thus, the array will become $[1,1,2,1]$, equal to $T$.
• For $S=[1,2,1,1]$, Simons will choose $[1,4]$.
• For $S=[1,1,2,1]$, Simons will choose $[1,2]$, $[3,3]$, and $[4,4]$.
• For $S=[1,1,1,2]$, Simons will choose $[1,2]$ and $[3,4]$.

In the second test case, we can see only the following arrays can be transformed to $T$:

• For $S=[1,1,3,2]$, Simons will choose $[1,1]$ and $[2,4]$.
• For $S=[1,2,1,3]$, Simons will choose $[1,1]$, $[2,2]$, and $[3,4]$.
• For $S=[1,2,3,1]$, Simons will choose $[1,1]$, $[2,2]$, $[3,3]$, and $[4,4]$.
• For $S=[1,3,2,1]$, Simons will choose $[1,4]$.
• For $S=[2,1,1,3]$, Simons will choose $[1,2]$ and $[3,4]$.
• For $S=[2,1,3,1]$, Simons will choose $[1,2]$, $[3,3]$, and $[4,4]$.
• For $S=[3,2,1,1]$, Simons will choose $[1,3]$ and $[4,4]$.

在第一个测试用例中，我们只能看到以下数组可以被变换为 $T$：

• 对于 $S=[2,1,1,1]$，Simon 将选择区间 $[1,3]$ 和 $[4,4]$。于是，该数组将变为 $[1,1,2,1]$，与 $T$ 相等。
• 对于 $S=[1,2,1,1]$，Simon 将选择区间 $[1,4]$。
• 对于 $S=[1,1,2,1]$，Simon 将选择区间 $[1,2]$、$[3,3]$ 和 $[4,4]$。
• 对于 $S=[1,1,1,2]$，Simon 将选择区间 $[1,2]$ 和 $[3,4]$。

在第二个测试用例中，我们只能看到以下数组可以被变换为 $T$：

• 对于 $S=[1,1,3,2]$，Simon 将选择区间 $[1,1]$ 和 $[2,4]$。
• 对于 $S=[1,2,1,3]$，Simon 将选择区间 $[1,1]$、$[2,2]$ 和 $[3,4]$。
• 对于 $S=[1,2,3,1]$，Simon 将选择区间 $[1,1]$、$[2,2]$、$[3,3]$ 和 $[4,4]$。
• 对于 $S=[1,3,2,1]$，Simon 将选择区间 $[1,4]$。
• 对于 $S=[2,1,1,3]$，Simon 将选择区间 $[1,2]$ 和 $[3,4]$。
• 对于 $S=[2,1,3,1]$，Simon 将选择区间 $[1,2]$、$[3,3]$ 和 $[4,4]$。
• 对于 $S=[3,2,1,1]$，Simon 将选择区间 $[1,3]$ 和 $[4,4]$。