D. Christmas Tree Decoration
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A group of $$$n$$$ people decided to decorate the Christmas tree. They have $$$(n+1)$$$ boxes of decorations, numbered from $$$0$$$ to $$$n$$$. Initially, the $$$i$$$-th box contains $$$a_i$$$ decorations.

We say that a permutation $$$p$$$ of size $$$n$$$ (an array of size $$$n$$$ where each number from $$$1$$$ to $$$n$$$ appears exactly once) is fair if it is possible to hang all the decorations on the tree using the following process:

  • person $$$p_1$$$ takes a decoration either from box $$$0$$$ or from box $$$p_1$$$, and hangs it on the tree;
  • person $$$p_2$$$ takes a decoration either from box $$$0$$$ or from box $$$p_2$$$, and hangs it on the tree;
  • and so on;
  • after person $$$p_n$$$, person $$$p_1$$$ follows, and the process repeats until all the decoration are on the tree.

During this process, there should never be a situation where person $$$i$$$ needs to hang a decoration, but both box $$$0$$$ and box $$$i$$$ are empty. If such a situation cannot be avoided, the permutation is not fair. However, if the people can choose from which box to take a decoration during each step in such a way that this situation does not arise, then the permutation is fair.

Your task is to calculate the number of fair permutations. Since the answer may be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$).

The second line contains $$$(n+1)$$$ integers $$$a_0, a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$).

Output

For each test case, print a single integer — the number of fair permutations, taken modulo $$$998244353$$$.

Example
Input
4
3
1 2 1 0
3
1 0 2 0
1
2 5
4
6 1 4 2 1
Output
2
0
1
12
Note

In the first example, the fair permutations are $$$[1, 2, 3]$$$ and $$$[1, 3, 2]$$$.

Let's take a closer look at the Christmas tree decoration for permutation $$$[1, 3, 2]$$$:

  • the person $$$p_1=1$$$ hangs a decoration from the box $$$1$$$;
  • the person $$$p_2=3$$$ hangs a decoration from the box $$$0$$$;
  • the person $$$p_3=2$$$ hangs a decoration from the box $$$2$$$;
  • the person $$$p_1=1$$$ hangs a decoration from the box $$$1$$$.

Note that if the person $$$p_1=1$$$ takes the decoration from the box $$$0$$$ during the first step, then the person $$$p_2=3$$$ won't be able to perform the next step (since both boxes $$$0$$$ and $$$3$$$ will be empty). However, since this situation can be avoided, the permutation is fair.