Yahya 是一个聪明的孩子，当他玩玩具时，他的脑海中总会浮现出许多有趣的问题。今天的问题源于他父亲送给他的一套火车车厢玩具，每节车厢的一侧都写有一个小写字母。

当他第一次看到这份礼物时，他很开心，并开始摆弄它们，随意地将车厢连接在一起。但过了一会儿，他像往常一样对这种漫无目的的玩法感到厌倦。于是，他决定定义一个有趣的新问题。

问题是，他目前有 $N$ 组连接好的车厢。他可以将每一组连接好的车厢表示为一个由小写字母组成的字符串。他想计算将所有 $N$ 组车厢连接成一列“有效”火车的方案数。如果一列火车中所有相同的字符都彼此相邻，则该火车是有效的。

上图展示了 Yahya 将车厢 "ab"、"bc" 和 "cd" 连接成有效火车的一种方式："ab bc cd"。如果他以 "cd ab bc" 的顺序连接它们，则该火车是无效的：字符 "c" 将不会彼此相邻。

你一定已经注意到，这对 Yahya 来说不是一个容易解决的问题，所以他需要你的帮助（他相信你一定能帮到他！）。就是这样，去帮助 Yahya 吧！

说明：字母只写在车厢的一侧，因此你不能将它们反转。例如，如果一节车厢上写着 "ab"，它不能被改变为 "ba"。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示连接好的车厢组数。下一行包含 $N$ 个由空格分隔的字符串。每个给定的字符串代表一组连接好的车厢，且仅由小写英文字母组成。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是获得有效火车的不同方案数。由于这个数字可能非常大，请输出该数字对 $1,000,000,007$ 取模的结果。

数据范围

$1 \le T \le 100$。 $1 \le$ 每组连接车厢的长度 $\le 100$。

小数据（10 分）

$1 \le N \le 10$。

大数据（25 分）

$1 \le N \le 100$。

样例

样例输入 1

3
3
ab bbbc cd
4
aa aa bc c
2
abc bcd

样例输出 1

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

说明

在第一个样例中，只有一种方法可以通过按顺序连接字符串 "ab"、"bbbc" 和 "cd" 来形成有效火车。

在第二个样例中，有 4 种可能的方法来形成有效火车。注意，有两个由字符串 "aa" 表示的不同连接车厢组，因此有两种不同的方式来排列这两个字符串并将它们组合成一组连接的车厢 "aaaa"。此外，将车厢组 "bc" 与 "c" 连接成 "bcc" 只有一种方式。之后，你可以以两种不同的方式排列 "aaaa" 和 "bcc"。因此，总共有 $2 \times 2 = 4$ 种形成有效火车的方法。

在第三个样例中，没有办法形成有效火车，因为如果以 "abc"+"bcd" 或 "bcd"+"abc" 这两种方式中的任何一种连接，都会出现两个 "b" 和两个 "c" 不连续的情况。