P4590 [TJOI2018] Funfair

Xiaodou participated in the NOI funfair. At the venue, each time he completes an activity he receives a medal, and each medal is labeled only with $\texttt{N}$, $\texttt{O}$, or $\texttt{I}$. At the venue he collected a string consisting of $K$ medals. The redemption rule is that the length of the longest common subsequence between the medal string and a redemption string is Xiaodou’s final reward level. It is known that the redemption string has length $N$, and the substring $\texttt{NOI}$ never appears in the redemption string, i.e., there is no occurrence of $\texttt{NOI}$. Now Xiaodou wants to know, for each reward level, how many different valid redemption strings correspond to it.

The first line contains two integers, $N, K$, representing the length of the redemption string and the length of the medal string Xiaodou collected ($N\leq1000,K\leq15$). The second line contains $K$ characters, representing the medal string Xiaodou obtained.

Output $K+1$ lines. The $i$-th line is the number of different valid redemption strings for which Xiaodou’s final reward level is $i-1$. This number can be large; output the result modulo $10^9+7$.

Sample explanation: Strings whose longest common subsequence length is $0$: $\texttt{III}$. Strings whose longest common subsequence length is $2$: $\texttt{NON}$, $\texttt{NNO}$, $\texttt{NOO}$, $\texttt{ONO}$, $\texttt{INO}$, $\texttt{NIO}$. Excluding $\texttt{NOI}$, the remaining $19 = 26-6-1$ kinds have a longest common subsequence length of $1$. Constraints - For $10\%$ of the testdata, $N\leq10,K\leq10$. - For $30\%$ of the testdata, $N\leq100,K\leq4$. - For $100\%$ of the testdata, $N\leq1000,K\leq15$. Translated by ChatGPT 5