Natalia 和 Cezary 喜欢玩游戏，尤其是他们自己发明的游戏。他们决定摆放一排硬币堆，每堆包含 $m$ 枚硬币，每枚硬币要么是蓝色的，要么是红色的。在 Natalia 的回合中，她可以选择任意一枚蓝色硬币，并将该硬币及其上方堆中的所有硬币从游戏中移除。同样，在 Cezary 的回合中，他可以选择任意一枚红色硬币，并将该硬币及其上方堆中的所有硬币从游戏中移除。玩家轮流进行操作，无法进行合法操作（即所有硬币已被移除）的玩家输掉比赛。

了解规则后，他们现在必须确定游戏的初始状态——一个包含 $d$ 堆硬币的序列，每堆恰好包含 $m$ 枚硬币。Natalia 和 Cezary 都不想拥有不公平的优势，因此他们一致认为硬币堆序列必须是“公平的”。如果假设 Natalia 和 Cezary 都采取最优策略，后手玩家（即不先手行动的玩家）获胜，则称该硬币堆序列是公平的。也就是说，如果 Natalia 先手，则在最优策略下 Cezary 获胜；反之，如果 Cezary 先手，则 Natalia 获胜。

他们已经摆放好了前 $k$ 堆硬币，每堆 $m$ 枚。现在他们想知道如何完成这个序列。他们已经得出结论，游戏中的硬币堆总数不超过 $n$ 是合理的。请帮助他们，对于区间 $[k, n]$ 中的每个 $d$，计算有多少种不同的公平的 $d$ 堆硬币序列，这些序列以他们已经摆放好的硬币堆开头。如果存在 $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$ 行包含一个长度恰好为 $m$ 的字符串，由字符 ‘N’ 和 ‘C’ 组成，表示第 $i$ 堆硬币从下往上的颜色。如果第 $j$ 个字符是 ‘N’，则第 $i$ 堆中从下往上数第 $j$ 枚硬币是蓝色的。否则，该字符为 ‘C’，表示该硬币是红色的。

输出格式

输出一行，包含 $n - k + 1$ 个整数，其中第 $i$ 个数表示将序列延长 $i - 1$ 堆，使得最终序列公平的方法数，结果对 $10^9 + 7$ 取模。

样例

样例输入 1

3 3 1
CCN

样例输出 1

0 1 3

样例输入 2

2 1 0

样例输出 2

1 0 2

样例输入 3

4 2 4
CN
NC
CC
NN

样例输出 3

1

说明

在第一个样例中，如果不增加任何硬币堆，单堆序列是不公平的。我们可以增加一个 NNC 堆，这样两堆序列就是公平的。增加两堆的方法有三种：[CCN, NNN], [NNN, CCN], [NCN, NCN]。

子任务

• 在某些测试组中，$k = n$。
• 在某些测试组中，$n \le 8$ 且 $m \le 8$。
• 在某些测试组中，$n \le 12$ 且 $m \le 13$。
• 在某些测试组中，$n \le 16$ 且 $m \le 19$。

上述每种情况至少描述了一组未在先前情况中提到的测试组。