Description

我们总共要烹饪 $\mathbf{N}$ 张煎饼。这些煎饼的半径分别为 $1$ 厘米（cm）、$2 \mathrm{~cm}$、$3 \mathrm{~cm}$，……，以及 $\mathbf{N} \mathrm{cm}$，但烹饪顺序不一定按半径从小到大排列。烹饪完第一张煎饼后，我们直接将其放在盘子上。之后每烹饪完一张煎饼，就将其叠放在之前所有煎饼的最上方，且所有煎饼的中心对齐。这样，每张煎饼在刚被加入时都能从顶部被看到。只有当之后烹饪了比它半径更大的煎饼时，这张煎饼才会被隐藏。

例如，假设我们烹饪 4 张煎饼。首先烹饪半径为 $3 \mathrm{~cm}$ 的煎饼，此时它可见。接着烹饪半径为 $1 \mathrm{~cm}$ 的煎饼，叠放在第一张煎饼上，此时两张煎饼都可见。然后烹饪半径为 $2 \mathrm{~cm}$ 的煎饼，它会覆盖前一张煎饼（半径为 $1 \mathrm{~cm}$ 的煎饼），但不会覆盖第一张煎饼，因此此时共有 2 张煎饼可见。最后，烹饪半径为 $4 \mathrm{~cm}$ 的煎饼，它会覆盖所有其他煎饼，此时只有 1 张煎饼可见。下图展示了每张煎饼被烹饪后叠放的状态，其中完全不透明的煎饼表示可见，半透明的煎饼表示不可见。

设 $\mathbf{V}_{\mathbf{i}}$ 表示叠放了恰好 $i$ 张煎饼时可见的煎饼数量。在上面的例子中，$\mathbf{V}_{1}=1$、$\mathbf{V}_{2}=2$、$\mathbf{V}_{3}=2$、$\mathbf{V}_{4}=1$。

给定列表 $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$，问在所有 $\mathbf{N} !$ 种可能的烹饪顺序中，有多少种顺序能恰好得到给定的 $\mathbf{V}_{\mathbf{i}}$ 序列？由于结果可能非常大，只需输出结果对质数 $10^{9}+7$（即 $1000000007$）取模后的值。

Input Format

输入的第一行包含测试用例数量 $\mathbf{T}$。每个测试用例包含两行：第一行是一个整数 $\mathbf{N}$，表示烹饪的煎饼数量；第二行包含 $\mathbf{N}$ 个整数 $\mathbf{V}_{1}, \mathbf{V}_{2}, \ldots, \mathbf{V}_{\mathbf{N}}$，分别表示叠放了 $1, 2, \ldots, \mathbf{N}$ 张煎饼时的可见煎饼数量。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足条件的烹饪顺序数量对 $10^{9}+7$ 取模后的结果。

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

Hint

样例解释

样例 #1 已在题目描述中说明，唯一的满足条件的烹饪顺序是 $3,1,2,4$。

在样例 #2 中，顺序 $1,3,2$ 和 $2,3,1$ 均能满足给定的 $\mathbf{V}_{\mathbf{i}}$ 序列。下图展示了这两种情况：

在样例 #3 中，叠加第二张煎饼后只有 1 张煎饼可见，因此无法通过叠加第三张煎饼使可见煎饼数量超过 2。

样例测试集 2 符合测试集 2 的限制条件，但提交的解法不会实际运行该测试集。

在测试集 2 的样例中，共有 $316234143225$ 种烹饪顺序满足给定的 $\mathbf{V}_{\mathbf{i}}$ 序列，对 $10^{9}+7$ 取模后的结果是 $234141013$。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• 对于所有 $i$，$1 \leq \mathbf{V}_{\mathbf{i}} \leq i$。

测试集 1（可见判定）

• 时间限制：30 秒。
• $2 \leq \mathbf{N} \leq 13$。

测试集 2（隐藏判定）

• 时间限制：40 秒。
• $2 \leq \mathbf{N} \leq 10^{5}$。

翻译由 DeepSeek V3 完成