CFCF2205E.Simons and Dividing the Rhythm

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

我紧握手中的烦恼，然后将它们抛向千里之外。

—— SHUN，《ONMYWAY》

假设 Simons 有一个长度为 $m$ 的数组 $a$ 。

Simons 需要对该数组执行如下操作，且仅能执行一次：

首先，他需要选择一个整数 $k$ $k$ ，并选定 $k$ $k$ 对整数 $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ $[l_{1}, r_{1}], [l_{2}, r_{2}], \dots, [l_{k}, r_{k}]$ ，使得：
- 对每个 $1\le i\le k$ ，都有 $l_i\le r_i$ ；
- $l_1=1$ ， $r_k=m$ ；
- 对每个 $i$ （ $1 \leq i < k$ ）， $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$ 。请你统计有多少个数组 $S$ ，经过 Simons 执行如上的一次操作后，可以变换为 $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$ 取模。

输入#1

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

输出#1

对于第一个测试用例，只有如下几种数组能够被变换为 $T$ ：

对于第二个测试用例，只有如下几种数组能够被变换为 $T$ ：