CF2205E Simons and Dividing the Rhythm

I grip my troubles within my hand, then hurl them off a thousand lands. — SHUN, [ONMYWAY](https://open.spotify.com/track/0ZOaDlRReh6qeZWipAMHDu) 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 $ .

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 $ .

For each test case, output a single integer — the number of arrays $ S $ , modulo $ 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] $ .