P13037 [GCJ 2021 #2] Hidden Pancakes

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

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