我把烦恼握在手中,然后将它们从一千个土地上扔掉。
— 顺, ONMYWAY
考虑给 Simons 一个大小为 $$$m$$$ 的数组 $$$a$$$。
Simons 必须对数组进行操作 正好一次 如下:
- 首先,他必须选择一个整数 $$$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}$$$ 对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$。
- 然后,他独立地反转每个子数组$$$[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 可以将 $$$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$$$ 为模。
示例
输入复制
541 1 2 141 2 3 161 3 2 3 3 2102 3 1 4 3 1 4 3 1 218000
输出复制
47223831
注意
在第一个测试用例中,我们可以看到只有以下数组可以转换为$$$T$$$:
- 对于 $$$S=[2,1,1,1]$$$,Simons 将选择 $$$[1,3]$$$ 和 $$$[4,4]$$$。因此,该数组将变为$$$[1,1,2,1]$$$,等于$$$T$$$。
- 对于 $$$S=[1,2,1,1]$$$,Simons 将选择 $$$[1,4]$$$。
- 对于 $$$S=[1,1,2,1]$$$,Simons 将选择 $$$[1,2]$$$、$$$[3,3]$$$ 和 $$$[4,4]$$$。
- 对于 $$$S=[1,1,1,2]$$$,Simons 将选择 $$$[1,2]$$$ 和 $$$[3,4]$$$。
在第二个测试用例中,我们可以看到只有以下数组可以转换为$$$T$$$:
- 对于 $$$S=[1,1,3,2]$$$,Simons 将选择 $$$[1,1]$$$ 和 $$$[2,4]$$$。
- 对于 $$$S=[1,2,1,3]$$$,Simons 将选择 $$$[1,1]$$$、$$$[2,2]$$$ 和 $$$[3,4]$$$。
- 对于 $$$S=[1,2,3,1]$$$,Simons 将选择 $$$[1,1]$$$、$$$[2,2]$$$、$$$[3,3]$$$ 和 $$$[4,4]$$$。
- 对于 $$$S=[1,3,2,1]$$$,Simons 将选择 $$$[1,4]$$$。
- 对于 $$$S=[2,1,1,3]$$$,Simons 将选择 $$$[1,2]$$$ 和 $$$[3,4]$$$。
- 对于 $$$S=[2,1,3,1]$$$,Simons 将选择 $$$[1,2]$$$、$$$[3,3]$$$ 和 $$$[4,4]$$$。
- 对于 $$$S=[3,2,1,1]$$$,Simons 将选择 $$$[1,3]$$$ 和 $$$[4,4]$$$。