G. Выбывание игроков
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В некоторой игре участвуют $$$n$$$ игроков, пронумерованных от $$$1$$$ до $$$n$$$. У каждого игрока есть сила — целое число от $$$1$$$ до $$$n$$$. Силы всех игроков различны. Распределение сил задаётся перестановкой $$$(s_1, s_2, \ldots, s_n)$$$, где $$$s_j$$$ — сила игрока $$$j$$$.

Изначально все игроки участвуют в игре. Игра состоит из $$$n-1$$$ раундов. В раунде $$$i$$$ игрок с номером $$$a_i$$$ является защищённым. Защищённым может быть и игрок, который уже выбыл из игры.

В каждом раунде выбывает ровно один игрок. Его выбирают следующим образом:

  • если игрок с минимальной силой среди оставшихся не является защищённым, он выбывает;
  • иначе выбывает игрок со второй минимальной силой среди оставшихся.

Выбывший игрок больше не участвует в игре. После последнего раунда остаётся ровно один игрок.

Вам дана последовательность $$$a_1, a_2, \ldots, a_{n-1}$$$, но распределение сил неизвестно. Для каждого игрока $$$j$$$ и каждого раунда $$$i$$$ найдите количество перестановок $$$(s_1, s_2, \ldots, s_n)$$$, при которых игрок $$$j$$$ выбывает в раунде $$$i$$$.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 2500$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 5000$$$) — количество игроков;
  • вторая строка содержит $$$n-1$$$ целых чисел $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — номера защищённых игроков в соответствующих раундах. Значения $$$a_i$$$ могут повторяться.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Выходные данные

Для каждого набора входных данных выведите ответ следующим образом:

Обозначим через $$$ans(i,j)$$$ количество перестановок $$$(s_1, s_2, \ldots, s_n)$$$, при которых игрок $$$i$$$ выбывает в раунде $$$j$$$, взятое по модулю $$$998\,244\,353$$$. Выведите одно целое число, равное $$$\oplus_{i=1}^{n} \oplus_{j=1}^{n-1} (ans(i,j)\cdot i\cdot j)$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ (XOR). Только значения $$$ans(i,j)$$$ берутся по модулю $$$998\,244\,353$$$; произведения $$$ans(i,j)\cdot i\cdot j$$$ и итоговый ответ по модулю не берутся.

Пример
Входные данные
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
Выходные данные
2
3
96
188
2024
4610
69
Примечание

В первом наборе входных данных есть два возможных распределения сил: $$$(1,2)$$$ и $$$(2,1)$$$. В единственном раунде защищён игрок $$$2$$$, поэтому в обоих случаях выбывает игрок $$$1$$$. Таким образом, $$$ans(1,1)=2$$$, $$$ans(2,1)=0$$$, а ответ равен $$$$$$ (2\cdot 1\cdot 1)\oplus(0\cdot 2\cdot 1)=2. $$$$$$

Во втором наборе входных данных есть $$$6$$$ возможных распределений сил. Значения $$$ans(i,j)$$$ приведены в таблице: строки соответствуют игрокам, столбцы — раундам. $$$$$$ \begin{array}{c|cc} & j=1 & j=2 \\ \hline i=1 & 0 & 5 \\ i=2 & 3 & 0 \\ i=3 & 3 & 1 \end{array} $$$$$$ Игрок $$$1$$$ защищён в первом раунде, а игрок $$$2$$$ — во втором, поэтому соответствующие значения равны нулю. Во втором раунде игрок $$$1$$$ выбывает при пяти распределениях сил, а игрок $$$3$$$ — только при распределении $$$(3,1,2)$$$. После умножения значений таблицы на номера игрока и раунда получаем ответ $$$$$$ 0\oplus 10\oplus 6\oplus 0\oplus 9\oplus 6=3. $$$$$$

В третьем наборе входных данных есть $$$24$$$ возможных распределения сил. Игрок $$$1$$$ защищён во всех раундах и никогда не выбывает. Остальные три игрока равноправны, поэтому каждый из них выбывает в каждом раунде при $$$24/3=8$$$ распределениях сил. Таблица значений $$$ans(i,j)$$$ имеет вид $$$$$$ \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} $$$$$$ Произведения для игрока $$$1$$$ равны нулю. XOR произведений для остальных игроков даёт ответ $$$$$$ 16\oplus 32\oplus 48\oplus 24\oplus 48\oplus 72\oplus 32\oplus 64\oplus 96=96. $$$$$$