题目描述

题目译自 PA 2024 Runda 5 Monety

Natalia 和 Cezary 喜欢玩游戏，尤其是他们自己发明的游戏。他们决定在自己面前放置一些堆硬币，硬币从上到下排成类似栈的样子，每堆有 $m$ 枚硬币，每枚硬币要么是蓝色的，要么是红色的。

轮到 Natalia 时，她可以选择一枚蓝色硬币，并将其连同其上方的所有硬币一起从硬币堆中移除。 轮到 Cezary 时，他可以选择一枚红色硬币，并将其连同其上方的所有硬币一起从硬币堆中移除。 玩家轮流操作，不能采取合法操作的玩家就输——也就是说，当一位玩家操作时所有硬币都已被移除。

现在他们知道了规则，他们必须确定游戏的初始状态——$d$ 堆硬币，每堆恰好包含 $m$ 个硬币。Natalia 和 Cezary 都不希望拥有不公平的优势，因此他们一致认为硬币的顺序应该是公平的。 假设 Natalia 和 Cezary 都采取最优策略，后手赢得游戏，则称初始状态是公平的。也就是说：

如果 Natalia 先手，则采用最优策略的 Cezary 将获胜；

如果 Cezary 先手，则采用最优策略的 Natalia 将获胜。

两人已经摆好了前 $k$ 堆 $m$ 个硬币。现在他们正在思考如何完成这一系列硬币堆。他们已经得出结论，游戏中拥有超过 $n$ 堆硬币是没有意义的。

帮助他们，对于区间 $[k, n]$ 中的每个整数 $d$，告诉他们有多少种不同的由 $d$ 堆 $m$ 枚硬币组成的公平初始状态，这些初始状态从他们已经摆好的硬币堆开始。 如果存在 $i \in [1, d]$ 和 $j \in [1, m]$，当第 $i$ 堆中的第 $j$ 个硬币在一种排列方式中为蓝色，在另一种为红色，则认为这两个初始排列方式是不同的。

由于答案可能很大，输出答案对 $10^9+7$ 取模后的值即可。

输入格式

第一行三个整数 $n$, $m$ 和 $k$（$1 \le n \le 32$，$1 \le m \le 24$，$0 \le k \le n$），分别表示硬币堆的最大值，每堆中硬币个数和已经摆好的硬币堆数。

接下来 $k$ 行描述已经摆好的硬币堆，第 $i$ 行包含一个仅由 N 和 C 组成且长度为 $m$ 的字符串，表示从底部起第 $i$ 堆硬币的摆放方式。如果第 $j$ 个字符为 N，则第 $i$ 堆硬币自底向上数第 $j$ 个硬币为蓝色，否则，这个字符为 C，表示硬币为红色。

输出格式

输出一行 $n-k+1$ 个整数，第 $i$ 个整数表示再摆 $i-1$ 堆硬币，以满足最终摆放方式是公平的最终摆放方式数。输出对 $10^9+7$ 取模。

样例 1

3 3 1
CCN

0 1 3

如果我们不添加任何硬币堆，则最初局面不是公平的。然而，我们可以加一堆排列为 NNC 的硬币——这样两堆硬币的初始状态就是公平的了。我们可以以三种方式添加两堆硬币：[CCN, NNN]、[NNN, CCN] 和 [NCN, NCN]。

样例2

2 1 0

1 0 2

样例3

4 2 4
CN
NC
CC
NN

1

数据规模与约定

在某些子任务中，满足 $k = n$。 在某些子任务中，满足 $n \le 8$，$m \le 8$。 在某些子任务中，满足 $n \le 12$，$m \le 13$。 在某些子任务中，满足 $n \le 16$，$m \le 19$。 上述每个子任务至少描述了之前子任务中没有出现的一组。