CF2182D.Christmas Tree Decoration

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

有 $n$ 个人决定装饰圣诞树。他们共有 $(n+1)$ 盒装饰品，编号从 $0$ 到 $n$。初始时，第 $i$ 个盒子中有 $a_i$ 个装饰品。

我们称一个大小为 $n$ 的排列 $p$（即一个长度为 $n$ 的数组，其中数字 $1$ 到 $n$ 各恰好出现一次）是公平的，如果可以按如下过程将所有装饰品挂到树上：

• 第 $p_1$ 个人从第 $0$ 号盒子或第 $p_1$ 号盒子中取一个装饰品，并将其挂到树上；
• 第 $p_2$ 个人从第 $0$ 号盒子或第 $p_2$ 号盒子中取一个装饰品，并将其挂到树上；
• 依此类推；
• 在第 $p_n$ 个人之后，再次轮到第 $p_1$ 个人，如此循环，直到所有装饰品都已挂上树。

在整个过程中，绝不能出现如下情形：某位第 $i$ 个人需要挂一个装饰品，但第 $0$ 号盒子和第 $i$ 号盒子此时均为空。若该情形不可避免，则该排列不为公平排列；反之，若人们能在每一步自主选择从哪个盒子取装饰品，从而始终避免该情形发生，则该排列是公平的。

你的任务是计算公平排列的总数。由于答案可能很大，请对 $998244353$ 取模后输出。

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

第一行包含一个整数 $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$）。

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

对于每个测试用例，输出一个整数——公平排列的数量对 $998244353$ 取模的结果。

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.

在第一个例子中，公平排列为 $[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$ 均为空）。然而，由于这种情况可以避免，该排列仍被视为公平的。