题目描述

We are cooking $\mathbf{N}$ pancakes in total. We cook one pancake with a 1 centimeter (cm) radius, one with a $2 \mathrm{~cm}$ radius, one with a $3 \mathrm{~cm}$ radius, ..., and one with an $\mathbf{N} \mathrm{cm}$ radius, not necessarily in that order. After we cook the first pancake, we just lay it on a plate. After we cook each subsequent pancake, we lay it on top of the previously made pancake, with their centers coinciding. In this way, a pancake is visible from the top of the stack when we first add it. A pancake only becomes hidden if we later cook another pancake with a larger radius.

For example, say we cook 4 pancakes. We first cook the pancake with radius $3 \mathrm{~cm}$, and it is visible. Then, we cook the pancake with radius $1 \mathrm{~cm}$, lay it on top of the first one and both are visible. Third, we cook the pancake with radius $2 \mathrm{~cm}$, and now that covers the previous pancake, but not the first one, so 2 pancakes remain visible in total. Finally, we cook the pancake with radius $4 \mathrm{~cm}$ which covers the other pancakes leaving only 1 visible pancake. The picture below illustrates the state of the stack after each pancake is cooked. Within each stack, the fully colored pancakes are visible and the semi-transparent pancakes are not visible.

Let $\mathbf{V}_{\mathbf{i}}$ be the number of visible pancakes when the stack contains exactly $i$ pancakes. In the example above, $\mathbf{V}_{1}=1, \mathbf{V}_{2}=2, \mathbf{V}_{3}=2$, and $\mathbf{V}_{4}=1$.

Given the list $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$, how many of the $\mathbf{N} !$ possible cooking orders yield those values? Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime $10^{9}+7(1000000007)$.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow, each described with two lines. The first line of a test case contains a single integer $\mathbf{N}$, the number of pancakes we cook. The second line of a test case contains $\mathbf{N}$ integers $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$, representing the number of visible pancakes after we cook $1,2, \ldots, \mathbf{N}$ pancakes, respectively.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of cooking orders of $\mathbf{N}$ pancakes that yield the given numbers of visible pancakes after each step, modulo the prime $10^{9}+7(1000000007)$.

3
4
1 2 2 1
3
1 1 2
3
1 1 3

Case #1: 1
Case #2: 2
Case #3: 0

1
24
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

Case #1: 234141013

提示

Sample Case #1 is explained in the problem statement. The order $3,1,2,4$ is the only one that yields the given $\mathbf{V}_{\mathbf{i}} \mathrm{s}$.

In Sample Case #2, both the order $1,3,2$ and the order $2,3,1$ yield the intended $\mathbf{V}_{\mathbf{i}} \mathrm{s}$. The pictures below illustrate both options.

In Sample Case #3, only 1 pancake is visible after the second is made, so there is no way to have more than 2 visible pancakes by only adding a third.

Sample Test Set 2 fits the limits of Test Set 2. It will not be run against your submitted solutions.

In the Sample Case for Test Set 2, there are $316234143225$ cooking orders that yield the given $\mathbf{V}_{\mathbf{i}} \mathrm{s}$. Modulo $10^{9}+7$, this value is $234141013$.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $1 \leq \mathbf{V}_{\mathbf{i}} \leq i$, for all $i$.

Test Set 1 (Visible Verdict)

• Time limit: 30 seconds.
• $2 \leq \mathbf{N} \leq 13$.

Test Set 2 (Hidden Verdict)

• Time limit: 40 seconds.
• $2 \leq \mathbf{N} \leq 10^{5}$.