P16659 [GKS 2018 #H] Big Buttons

你是一个热门新游戏节目的参赛者，正在为赢得大奖而战！ 有两个大按钮，一个红色，一个黑色。你将进行恰好 $N$ 次按钮按动。 你可以做出许多不同的按动序列，但有 $P$ 个**禁止前缀**，每个前缀的长度不超过 $N$。如果你的按动序列以任何一个禁止序列开头，你将无法赢得大奖。只要禁止前缀不出现在序列开头，序列中包含一个或多个禁止前缀是可以的。 获胜序列必须恰好包含 $N$ 次按钮按动，并且不能以任何一个禁止前缀开头。有多少种不同的获胜序列？

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

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

在第一个样例中，你必须进行 $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 完成