你将在外星行星上建造一个瓷砖马赛克地板。你将选择一个特定的矩形图案（包含 $R$ 行和 $C$ 列）的单位正方形瓷砖，然后为每个瓷砖从该行星上存在的 $K$ 种颜色中选择一种颜色；这些颜色编号为 $0$ 到 $K-1$。你将把该图案在水平和垂直方向上无限平铺。（也就是说，在完成的地板中，如果你选择了一个特定颜色的瓷砖，并且向上或向下移动 $R$ 个单元的任意倍数，或者向左或向右移动 $C$ 个单元的任意倍数，你最终会到达另一个颜色相同的瓷砖。）

当外星人心情愉快时，它能准确地感知颜色。然而，当外星人愤怒时，它会将第 $i$ 种颜色看作第 $P_i$ 种颜色，其中 $P$ 是 $0, 1, \dots, K-1$ 的一个排列。（$P_i$ 有可能等于 $i$。）为了避免混淆，你必须选择一个“无歧义”的图案，这意味着心情愉快和愤怒的外星人在观察地板时会看到相同的整体设计。也就是说，无论处于某种情绪状态的外星人站在地板上的什么位置，都必须存在另一个位置，让处于另一种情绪状态的外星人站在那里，并朝向相同的方向，使得他们两人看到的完全是相同的地板。

例如，假设地板由两种颜色（黑色和红色）的瓷砖组成，愤怒的外星人将黑色看作红色，将红色看作黑色。那么全黑的地板将是有歧义的，因为心情愉快的外星人会认为它是全黑的，而愤怒的外星人会认为它是全红的。然而，棋盘图案将是无歧义的，因为两种外星人看到的整体设计是相同的。

求出不同无歧义图案的数量，结果对 $1,000,000,007$ ($10^9+7$) 取模。如果两个图案的地板在仅经过水平和/或垂直平移后可以重合，则认为这两个图案是相同的（即不允许翻转和旋转）。

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例包含两行。 第一行包含三个整数 $K, R$ 和 $C$，如上所述。第二行包含 $K$ 个整数；其中第 $i$ 个整数是 $P_i$，表示颜色感知的排列。

输出格式

对于每个测试用例，输出一行包含 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是不同无歧义图案的数量，对 $1,000,000,007$ ($10^9+7$) 取模。

数据范围

• $1 \le T \le 100$
• $2 \le K \le 10^4$
• $1 \le R, C \le 10^6$

样例

样例输入 1

6
2 1 2
1 0
2 2 2
1 0
3 2 2
1 2 0
3 1 3
1 2 0
3 3 3
0 1 2
3 3 3
0 2 1

样例输出 1

Case #1: 1
Case #2: 3
Case #3: 0
Case #4: 2
Case #5: 2211
Case #6: 1

说明

在 Case #1 中，唯一的无歧义图案在两种不同颜色中各有一个单元格。 在 Case #2 中，三种不同的无歧义图案为：

00 01 01
11 01 10

任何其他图案要么是有歧义的，要么与上述三种图案之一相同（根据我们上面的定义）。 在 Case #4 中，两种不同的无歧义图案是 012 和 021。