D. Украшение новогодней елки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Группа из $$$n$$$ человек решила украсить новогоднюю елку. У них есть $$$(n+1)$$$ коробок с игрушками, пронумерованных от $$$0$$$ до $$$n$$$. Изначально в $$$i$$$-й коробке находится $$$a_i$$$ игрушек.

Скажем, что перестановка $$$p$$$ размера $$$n$$$ (массив размера $$$n$$$, где каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз) является честной, если возможно повесить все игрушки на елку, используя следующий процесс:

  • человек $$$p_1$$$ берет игрушку либо из коробки $$$0$$$, либо из коробки $$$p_1$$$, и вешает ее на елку;
  • человек $$$p_2$$$ берет игрушку либо из коробки $$$0$$$, либо из коробки $$$p_2$$$, и вешает ее на елку;
  • и так далее;
  • за человеком $$$p_n$$$ следует человек $$$p_1$$$, и процесс повторяется, пока все игрушки не окажутся на елке.

В ходе этого процесса не должно возникнуть ситуации, когда человек $$$i$$$ должен повесить игрушку, но и коробка $$$0$$$, и коробка $$$i$$$ пусты. Если такой ситуации избежать нельзя — перестановка не является честной. Если же люди могут выбирать, из какой коробки брать игрушку на каждом шаге, так, чтобы такой ситуации не возникло, то перестановка является честной.

Ваша задача — вычислить количество честных перестановок. Поскольку ответ может быть большим, выведите его по модулю $$$998244353$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$).

Вторая строка содержит $$$(n+1)$$$ целых чисел $$$a_0, a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$).

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

Для каждого набора входных данных выведите одно целое число — количество честных перестановок, взятое по модулю $$$998244353$$$.

Пример
Входные данные
4
3
1 2 1 0
3
1 0 2 0
1
2 5
4
6 1 4 2 1
Выходные данные
2
0
1
12
Примечание

В первом примере честными перестановками являются $$$[1, 2, 3]$$$ и $$$[1, 3, 2]$$$.

Давайте подробнее рассмотрим украшение елки для перестановки $$$[1, 3, 2]$$$:

  • человек $$$p_1=1$$$ вешает игрушку из коробки $$$1$$$;
  • человек $$$p_2=3$$$ вешает игрушку из коробки $$$0$$$;
  • человек $$$p_3=2$$$ вешает игрушку из коробки $$$2$$$;
  • человек $$$p_1=1$$$ вешает игрушку из коробки $$$1$$$.

Обратите внимание: если человек $$$p_1=1$$$ берет игрушку из коробки $$$0$$$ на первом шаге, то человек $$$p_2=3$$$ не сможет выполнить следующий шаг (так как и коробка $$$0$$$, и коробка $$$3$$$ будет пустой). Но так как этой ситуации можно избежать, перестановка является честной.