{"problem":{"name":"[PA 2024] Monety","description":{"content":"**题目译自 [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 喜欢玩游戏，尤其是他们自己发明的游戏。他们决定在自己面前放置一些堆硬币，硬币从上到下排成类似栈的样子","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":12000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10363"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [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/)**\n\nNatalia 和 Cezary 喜欢玩游戏，尤其是他们自己发明的游戏。他们决定在自己面前放置一些堆硬币，硬币从上到下排成类似栈的样子，每堆有 $m$ 枚硬币，每枚硬币要么是蓝色的，要么是红色的。轮到 Natalia 时，她可以选择一枚蓝色硬币，并将其连同其上方的所有硬币一起从硬币堆中移除。同样，在轮到 Cezary 时，他可以选择一枚红色硬币，并将其连同其上方的所有硬币一起从硬币堆中移除。 玩家将轮流操作，不能采取合法操作的玩家就输了——也就是说，当一位玩家操作的所有硬币都已被移除时。\n\n现在他们知道了规则，他们必须确定游戏的初始状态——$d$ 堆硬币，每堆恰好包含 $m$ 个硬币。Natalia 和 Cezary 都不希望拥有不公平的优势，因此他们一致认为硬币的顺序应该是公平的。假设 Natalia 和 Cezary 都采取最优策略，后手赢得游戏，则称初始状态是公平的。因此，如果 Natalia 先手，则采用最优策略的 Cezary 将获胜，反之亦然：如果 Cezary 先手，Natalia 将获胜。\n\n两人已经摆好了前 $k$ 堆 $m$ 个硬币。现在他们正在思考如何完成这一系列硬币堆。他们已经得出结论，游戏中拥有超过 $n$ 堆硬币是没有意义的。\n\n帮助他们，对于区间 $[k, n]$ 中的每个整数 $d$，告诉他们有多少种不同的由 $d$ 堆 $m$ 枚硬币组成的公平初始状态，这些初始状态从他们已经摆好的硬币堆开始。如果存在 $i\\in [1, d]$ 和 $j\\in [1, m]$，当第 $i$ 堆中的第 $j$ 个硬币在一种排列方式中为蓝色，在另一种为红色，则认为这两个初始排列方式是不同的。\n\n由于答案可能很大，输出答案对 $10^9+7$ 取模后的值即可。\n\n## Input\n\n第一行三个整数 $n,m$ 和 $k\\ (1\\le n\\le 32,1\\le m\\le 24,0\\le k\\le n)$，分别表示硬币堆的最大值，每堆中硬币个数和已经摆好的硬币堆数。\n\n接下来 $k$ 行描述已经摆好的硬币堆，第 $i$ 行包含一个仅由 `N` 和 `C` 组成且长度为 $m$ 的字符串，表示从底部起第 $i$ 堆硬币的摆放方式。如果第 $j$ 个字符为 `N`，则第 $i$ 堆硬币自底向上数第 $j$ 个硬币为蓝色，否则，这个字符为 `C`，表示硬币为红色。\n\n## Output\n\n输出一行 $n-k+1$ 个整数，第 $i$ 个整数表示再摆 $i-1$ 堆硬币，以满足最终摆放方式是公平的最终摆放方式数。输出对 $10^9+7$ 取模。\n\n[samples]\n\n## Background\n\nPA 2024 5A2\n\n## Note\n\n对于第一组样例，如果我们不添加任何硬币堆，则最初局面不是公平的。然而，我们可以加一堆排列为 `NNC` 的硬币——这样两堆硬币的初始状态就是公平的了。我们可以以三种方式添加两堆硬币：`[CCN, NNN]`，`[NNN, CCN]` 和 `[NCN, NCN]`。\n\n**数据范围与提示**\n\n- 在某些子任务中，满足 $k=n$。\n- 在某些子任务中，满足 $n\\le 8,m\\le 8$​。\n- 在某些子任务中，满足 $n\\le 12,m\\le 13$。\n- 在某些子任务中，满足 $n\\le 16,m\\le 19$​。\n\n上述每个子任务至少描述了之前子任务中没有出现的一组。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10363","tags":["2024","PA（波兰）"],"sample_group":[["3 3 1\nCCN\n","0 1 3\n"],["2 1 0\n","1 0 2\n"],["4 2 4\nCN\nNC\nCC\nNN\n","1\n"]],"created_at":"2026-03-03 11:09:25"}}