我们总共要制作 $N$ 个煎饼。我们制作一个半径为 $1$ 厘米 (cm) 的煎饼，一个半径为 $2$ cm 的煎饼，一个半径为 $3$ cm 的煎饼，……，以及一个半径为 $N$ cm 的煎饼，制作顺序不一定按半径大小。在制作第一个煎饼后，我们将其放在盘子上。在制作后续的每个煎饼时，我们将其放在之前制作的煎饼之上，并使它们的中心重合。这样，当我们第一次添加一个煎饼时，从堆叠的顶部看它是可见的。只有当我们随后制作了另一个半径更大的煎饼时，该煎饼才会变得不可见。

例如，假设我们制作 $4$ 个煎饼。我们首先制作半径为 $3$ cm 的煎饼，它是可见的。然后，我们制作半径为 $1$ cm 的煎饼，将其放在第一个煎饼之上，此时两个都可见。第三，我们制作半径为 $2$ cm 的煎饼，它覆盖了之前的煎饼，但没有覆盖第一个，因此总共有 $2$ 个煎饼可见。最后，我们制作半径为 $4$ cm 的煎饼，它覆盖了其他所有煎饼，只留下 $1$ 个可见的煎饼。下图展示了每个煎饼制作后堆叠的状态。在每个堆叠中，完全着色的煎饼是可见的，半透明的煎饼是不可见的。

令 $V_i$ 为堆叠中恰好包含 $i$ 个煎饼时的可见煎饼数量。在上面的例子中，$V_1 = 1, V_2 = 2, V_3 = 2, V_4 = 1$。

给定列表 $V_1, V_2, \dots, V_N$，有多少种可能的制作顺序能产生这些数值？由于输出可能是一个非常大的数字，我们仅要求你输出结果除以质数 $10^9 + 7$ ($1000000007$) 的余数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例，每个测试用例由两行描述。每个测试用例的第一行包含一个整数 $N$，表示我们制作的煎饼数量。每个测试用例的第二行包含 $N$ 个整数 $V_1, V_2, \dots, V_N$，分别表示制作 $1, 2, \dots, N$ 个煎饼后的可见煎饼数量。

输出格式

对于每个测试用例，输出一行包含 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是产生给定可见煎饼数量的 $N$ 个煎饼的制作顺序数量，对质数 $10^9 + 7$ ($1000000007$) 取模。

数据范围

$1 \le T \le 100$。 $1 \le V_i \le i$，对于所有 $i$。

测试集 1（可见判定） 时间限制：30 秒。 $2 \le N \le 13$。

测试集 2（隐藏判定） 时间限制：40 秒。 $2 \le N \le 10^5$。

样例

样例输入 1

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

样例输出 1

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

说明：样例 #1 在题目描述中已解释。顺序 $3, 1, 2, 4$ 是唯一能产生给定 $V_i$ 的顺序。 在样例 #2 中，顺序 $1, 3, 2$ 和顺序 $2, 3, 1$ 都能产生预期的 $V_i$。下图展示了这两种选择。

在样例 #3 中，制作第二个煎饼后只有 $1$ 个煎饼可见，因此在仅添加第三个煎饼的情况下，不可能有超过 $2$ 个可见煎饼。

附加样例 - 测试集 2

以下附加样例符合测试集 2 的限制。它不会在你的提交中运行。

样例输入 2

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

样例输出 2

Case #1: 234141013

说明：在测试集 2 的样例中，有 $316234143225$ 种制作顺序能产生给定的 $V_i$。对 $10^9 + 7$ 取模后，该值为 $234141013$。