题目描述

你是一个热门新游戏节目的参赛者，正在为赢得大奖而战！

有两个大按钮，一个红色，一个黑色。你将进行恰好 $N$ 次按钮按动。

你可以做出许多不同的按动序列，但有 $P$ 个禁止前缀，每个前缀的长度不超过 $N$。如果你的按动序列以任何一个禁止序列开头，你将无法赢得大奖。只要禁止前缀不出现在序列开头，序列中包含一个或多个禁止前缀是可以的。

获胜序列必须恰好包含 $N$ 次按钮按动，并且不能以任何一个禁止前缀开头。有多少种不同的获胜序列？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $P$，含义如上所述。随后有 $P$ 行，每行包含一个长度在 $1$ 到 $N$ 之间的字符串，描述一个禁止的按动序列。其中 R 表示按下红色按钮，B 表示按下黑色按钮。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是如上所述的获胜序列的数量。

3
3 2
BBB
RB
5 1
R
4 3
R
B
RBRB

Case #1: 5
Case #2: 16
Case #3: 0

1
50 5
BRBRBBBRBRRRBBB
BRBRBRRRBRRRBRB
BBBRBBBRBRRRBBB
BRBRBRRRBRRRB
BRBRBBBRBBBRB

Case #1: 1125556309458944

提示

在第一个样例中，你必须进行 $3$ 次按动。共有 $8$ 种可能的三个按动序列，但其中一些会使你输掉游戏。这些序列如下：

• RBB。该序列以第一个禁止前缀（RB）开头，因此被禁止。
• RBR。该序列以第一个禁止前缀（RB）开头，因此被禁止。
• BBB。该序列以第二个禁止前缀（BBB）开头，因此被禁止。

因此，只有 $5$ 种获胜序列。

在第二个样例中，你必须进行 $5$ 次按动。只有一个禁止前缀，即 R。这意味着第一次按动必须是 B，而接下来的 $4$ 次按动可以是任意按钮。总共得到 $16$ 种不同的按动序列。

在第三个样例中，你必须进行 $4$ 次按动。共有三个禁止前缀，但由于每个可能的序列要么以 R（第一个禁止前缀）开头，要么以 B（第二个禁止前缀）开头，因此没有获胜序列。故答案为 $0$。

限制条件

$1 \le T \le 100$。

$1 \le P \le \min(2^N, 100)$。

每个禁止前缀的长度在 $1$ 到 $N$ 之间（包含端点）。

没有两个禁止前缀相同。

小数据集（测试集 1 – 可见）

$1 \le N \le 10$。

大数据集（测试集 2 – 隐藏）

$1 \le N \le 50$。

翻译由 DeepSeek V4 Pro 完成