Description

Yahya 是一个聪明的孩子，所以在玩玩具的时候，他总会想到很多有趣的问题。今天的问题来源于他爸爸送给他的一组火车车厢，每节车厢的一侧都写有一个小写英文字母。

刚看到礼物时，Yahya 十分高兴，开始随意地把车厢连接起来玩。但没玩多久，他就像往常一样感到无聊——因为这个游戏没有目标。所以他决定自己定义一个有趣的问题。

这个问题是：他现在有 $N$ 组已经连接好的车厢。每组连接好的车厢可以用一个小写字母组成的字符串表示。他想要计算有多少种不同的方式可以把这 $N$ 组车厢连接成一列合法的火车。所谓合法的火车，是指每个字母在整列车厢中出现时，必须是连在一起的。

上图是 Yahya 连接 "ab"、"bbbc" 和 "cd" 成为一列合法火车的一种方式：即 "ab bbbc cd"。如果他用 "cd ab bbbc" 的顺序连接它们，则是不合法的，因为字母 "c" 的出现不连续。

你肯定已经注意到了，这个问题对 Yahya 来说并不容易，所以他需要你的帮助（而他相信你一定能帮上忙）！就是这样——去帮帮 Yahya 吧！

注意： 字母只写在车厢的一侧，因此不能翻转它们。比如，一个车厢写着 "ab"，就不能改为 "ba"。

Input Format

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

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将所有车厢组连接成一列合法火车的不同方式数。由于这个数可能非常大，请输出其对 $1,\!000,\!000,\!007$ 取模的结果。

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

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

Hint

样例解释

在第一个样例中，只有一种方式可以将车厢组合成合法火车，即按顺序连接字符串 "ab"、"bbbc"、"cd"。

而在第二个样例中，有 $4$ 种不同方式可以构成合法火车。注意，"aa" 这个字符串出现了两次，代表有两组车厢完全一样，因此它们的顺序可以互换并合并为一组 "aaaa"。而 "bc" 和 "c" 也可以以唯一的一种方式合并成 "bcc"。最后，你可以将 "aaaa" 和 "bcc" 有两种不同的顺序组合，因此总共有 $2 \times 2 = 4$ 种方式。

在第三个样例中，不存在任何方式可以组成合法火车。不论是按 "abc"+"bcd" 还是 "bcd"+"abc" 的顺序连接，字母 "b" 和 "c" 都会出现不连续的情况，因此都不合法。

限制条件

• $1 \leq T \leq 100$。
• 每组连接车厢的字符串长度 $\leq 100$。

Small 数据集（10 分）

• 时间限制：60 3 秒。
• $1 \leq N \leq 10$。

Large 数据集（25 分）

• 时间限制：120 5 秒。
• $1 \leq N \leq 100$。

翻译由 ChatGPT-4o 完成