熊猫先生对 $N$ 名候选人进行了一项调查。

在调查中，每位候选人都收到了一份包含 $M$ 个是非题的问卷。保证每位候选人对每个问题都回答了“是”（Yes）或“否”（No）。

熊猫先生喜欢多样性。如果一个问题至少有一名候选人回答“是”，且至少有一名候选人回答“否”，他就认为这是一个“好问题”。

现在熊猫先生收集了所有的问卷。他想根据调查结果进行一些统计分析。

因为熊猫先生非常懒，他想随机抽取一些问卷作为样本。对于每一个可能的问题子集（不包括空集），熊猫先生想知道：假设样本中的问卷是随机选择的（样本可以是问卷的任意子集，包括全集和空集，且每种情况被选中的概率相等），那么该子集中的所有问题都是“好问题”的概率是多少。

你能帮熊猫先生解决这个问题吗？

为了简化问题，你只需要计算：

$$(P_1 \cdot 2^N \pmod{1000000007}) \oplus (P_2 \cdot 2^N \pmod{1000000007}) \oplus \dots \oplus (P_{2^M-1} \cdot 2^N \pmod{1000000007})$$

其中 $P_i$ 表示第 $i$ 个问题子集是好问题子集的概率。显然 $P_i \cdot 2^N$ 总是一个整数。

“$\oplus$”即“按位异或”，对应 C/C++ 和 Java 中的 ^ 运算符。 “$\pmod{}$”即“取模”，对应 C/C++ 和 Java 中的 % 运算符。

输入格式

第一行输入一个整数 $T$，表示测试用例的数量。

接下来是 $T$ 个测试用例。每个测试用例包含两行：第一行包含两个整数 $N$（问卷数量）和 $M$（问题数量）。

第二行包含 $N$ 个字符串 $Q_1, Q_2, \dots, Q_N$，表示每份问卷的回答。每份问卷 $Q_i$ 由恰好 $M$ 个字符组成，每个字符可以是“Y”（代表“是”）或“N”（代表“否”）。

输出格式

对于每个测试用例，输出一行“Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是加权概率的异或和。

数据范围

• $1 \le T \le 20$
• $1 \le N \le 10^5$
• $1 \le M \le 15$

样例

样例输入 1

2
2 2
NY YN
4 2
NN NY YN YY

样例输出 1

Case #1: 1
Case #2: 7

说明

样例 #1：问题 1 是好问题的概率为 $\frac{1}{4}$，问题 2 是好问题的概率为 $\frac{1}{4}$，问题 1 和问题 2 同时是好问题的概率为 $\frac{1}{4}$。 因此答案为： $(1 \pmod{1000000007}) \oplus (1 \pmod{1000000007}) \oplus (1 \pmod{1000000007}) = 1$

样例 #2：问题 1 是好问题的概率为 $\frac{9}{16}$，问题 2 是好问题的概率为 $\frac{9}{16}$，问题 1 和问题 2 同时是好问题的概率为 $\frac{7}{16}$。 因此答案为： $(9 \pmod{1000000007}) \oplus (9 \pmod{1000000007}) \oplus (7 \pmod{1000000007}) = 7$