P10363 [PA 2024] Coins

PA 2024 5A2

**This problem is translated from [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Round 5 [Monety](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mon/).** Natalia and Cezary like playing games, especially games they invent themselves. They decided to place some piles of coins in front of them. In each pile, the coins are stacked from top to bottom like a stack, and each pile contains $m$ coins. Each coin is either blue or red. On Natalia's turn, she may choose a blue coin and remove it together with all coins above it from the pile. Similarly, on Cezary's turn, he may choose a red coin and remove it together with all coins above it from the pile. The players alternate turns. A player who cannot make a legal move loses—that is, when all coins of the color that player is allowed to remove have already been removed. Now that they know the rules, they must decide the initial position: $d$ piles of coins, each containing exactly $m$ coins. Natalia and Cezary do not want anyone to have an unfair advantage, so they agree that the coin order should be fair. Assume both Natalia and Cezary play optimally. The initial position is called fair if the second player wins the game. Therefore, if Natalia moves first, then Cezary (playing optimally) will win, and vice versa: if Cezary moves first, then Natalia will win. They have already arranged the first $k$ piles of $m$ coins. Now they are thinking about how to complete the sequence of piles. They have also concluded that having more than $n$ piles in the game makes no sense. Help them: for each integer $d$ in the range $[k, n]$, tell them how many different fair initial positions consisting of $d$ piles of $m$ coins start with the piles they have already arranged. Two initial arrangements are considered different if there exist $i\in [1, d]$ and $j\in [1, m]$ such that the $j$-th coin in the $i$-th pile is blue in one arrangement and red in the other. Since the answer can be very large, output it modulo $10^9+7$.

The first line contains three integers $n, m$ and $k\ (1\le n\le 32,1\le m\le 24,0\le k\le n)$, representing the maximum number of piles, the number of coins in each pile, and the number of piles that have already been arranged. The next $k$ lines describe the piles that have already been arranged. The $i$-th line contains a string of length $m$ consisting only of `N` and `C`, describing the arrangement of the $i$-th pile from the bottom. If the $j$-th character is `N`, then the $j$-th coin from the bottom in the $i$-th pile is blue. Otherwise, the character is `C`, meaning the coin is red.

Output one line with $n-k+1$ integers. The $i$-th integer means the number of ways to add $i-1$ more piles so that the final arrangement is fair. Output the results modulo $10^9+7$.

For the first sample, if we do not add any piles, then the initial position is not fair. However, we can add one pile arranged as `NNC`—then the initial position with two piles becomes fair. We can add two piles in three ways: `[CCN, NNN]`, `[NNN, CCN]` and `[NCN, NCN]`. **Constraints and Notes** - In some subtasks, $k=n$. - In some subtasks, $n\le 8,m\le 8$. - In some subtasks, $n\le 12,m\le 13$. - In some subtasks, $n\le 16,m\le 19$. Each subtask above includes at least one set of testdata that does not appear in the previous subtasks. Translated by ChatGPT 5