G. Elimination of Players
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In a certain game, there are $$$n$$$ players numbered from $$$1$$$ to $$$n$$$. Each player has a strength — an integer from $$$1$$$ to $$$n$$$. All players have distinct strengths. The distribution of strengths is given by a permutation $$$(s_1, s_2, \ldots, s_n)$$$, where $$$s_j$$$ is the strength of player $$$j$$$.

Initially, all players take part in the game. The game consists of $$$n-1$$$ rounds. In the $$$i$$$-th round, the player $$$a_i$$$ is protected. It is possible that the protected player was already eliminated.

In each round, exactly one player is eliminated. This player is chosen as follows:

  • if the player with the minimum strength among the remaining players is not protected, that player is eliminated;
  • otherwise, the player with the second minimum strength among the remaining players is eliminated.

An eliminated player no longer takes part in the game. After the last round, exactly one player remains.

You are given the sequence $$$a_1, a_2, \ldots, a_{n-1}$$$, but the distribution of strengths is unknown. For each player $$$j$$$ and each round $$$i$$$, find the number of permutations $$$(s_1, s_2, \ldots, s_n)$$$ for which the player $$$j$$$ is eliminated in the $$$i$$$-th round.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 2500$$$) — the number of test cases.

Each test case consists of two lines:

  • the first line contains one integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of players;
  • the second line contains $$$n-1$$$ integers $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — the numbers of the protected players in the corresponding rounds. The values $$$a_i$$$ may repeat.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.
Output

For each test case, print the answer in the following way:

Let $$$ans(i,j)$$$ denote the number of permutations $$$(s_1, s_2, \ldots, s_n)$$$ for which player $$$i$$$ is eliminated in round $$$j$$$, taken modulo $$$998\,244\,353$$$. Print one integer equal to $$$\oplus_{i=1}^{n} \oplus_{j=1}^{n-1} (ans(i,j)\cdot i\cdot j)$$$, where $$$\oplus$$$ denotes the bitwise exclusive OR (XOR) operation. Only the values $$$ans(i,j)$$$ are taken modulo $$$998\,244\,353$$$; the products $$$ans(i,j)\cdot i\cdot j$$$ and the final answer are not.

Example
Input
7
2
2
3
1 2
4
1 1 1
4
1 4 1
7
2 2 2 7 7 7
6
3 1 3 6 3
5
5 1 4 2
Output
2
3
96
188
2024
4610
69
Note

In the first test case, there are two possible distributions of strengths: $$$(1,2)$$$ and $$$(2,1)$$$. In the only round, player $$$2$$$ is protected, so in both cases player $$$1$$$ is eliminated. Thus, $$$ans(1,1)=2$$$, $$$ans(2,1)=0$$$, and the answer is $$$$$$ (2\cdot 1\cdot 1)\oplus(0\cdot 2\cdot 1)=2. $$$$$$

In the second test case, there are $$$6$$$ possible distributions of strengths. The values of $$$ans(i,j)$$$ are shown in the table: rows correspond to players, columns — to rounds. $$$$$$ \begin{array}{c|cc} & j=1 & j=2 \\ \hline i=1 & 0 & 5 \\ i=2 & 3 & 0 \\ i=3 & 3 & 1 \end{array} $$$$$$ Player $$$1$$$ is protected in the first round, and player $$$2$$$ — in the second, so the corresponding values are zero. In the second round, player $$$1$$$ is eliminated for five strength distributions, and player $$$3$$$ — only for the distribution $$$(3,1,2)$$$. After multiplying the table values by the player and round numbers, we get the answer $$$$$$ 0\oplus 10\oplus 6\oplus 0\oplus 9\oplus 6=3. $$$$$$

In the third test case, there are $$$24$$$ possible distributions of strengths. Player $$$1$$$ is protected in all rounds and is never eliminated. The other three players are symmetric, so each of them is eliminated in each round for $$$24/3=8$$$ strength distributions. The table of values $$$ans(i,j)$$$ is $$$$$$ \begin{array}{c|ccc} & j=1 & j=2 & j=3 \\ \hline i=1 & 0 & 0 & 0 \\ i=2 & 8 & 8 & 8 \\ i=3 & 8 & 8 & 8 \\ i=4 & 8 & 8 & 8 \end{array} $$$$$$ The products for player $$$1$$$ are zero. The XOR of the products for the remaining players gives the answer $$$$$$ 16\oplus 32\oplus 48\oplus 24\oplus 48\oplus 72\oplus 32\oplus 64\oplus 96=96. $$$$$$