P10363 [PA 2024] Monety

PA 2024 5A2

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Monety](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mon/)** 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$ 取模。

对于第一组样例，如果我们不添加任何硬币堆，则最初局面不是公平的。然而，我们可以加一堆排列为 `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$​。 上述每个子任务至少描述了之前子任务中没有出现的一组。