题目描述

小豆参加了 NOI 的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是 $\texttt{N}$、$\texttt{O}$、$\texttt{I}$ 的字样。在会场上他收集到了 $K$ 个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。现在已知兑奖串长度为 $N$，并且在兑奖串上不会出现连续三个奖章为 $\texttt{NOI}$，即奖章中不会出现子串 $\texttt{NOI}$。现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

输入格式

第一行两个数，$N, K$ 分别代表兑奖串的长度，小豆收集的奖章串的长度（$N\leq1000,K\leq15$）。

第二行一共 $K$ 个字符，表示小豆得到的奖章串。

输出格式

一共 $K+1$ 行，第 $i$ 行表示小豆最后奖励等级为 $i-1$ 的不同的合法兑奖串的个数，可能这个数会很大，结果对 $10^9+7$ 取模。

3 2
NO

1
19
6

提示

样例解释

最长公共子序列长度为 $0$ 的串有：$\texttt{III}$;

最长公共子序列长度为 $2$ 的串有：$\texttt{NON}$、$\texttt{NNO}$、$\texttt{NOO}$、$\texttt{ONO}$、$\texttt{INO}$、$\texttt{NIO}$；

除去 $\texttt{NOI}$，余下的 $19 = 26-6-1$ 种为最长公共子序列长度为 $1$。

数据范围

• 对于 $10\%$ 的数据，$N\leq10,K\leq10$；
• 对于 $30\%$ 的数据，$N\leq100,K\leq4$；
• 对于 $100\%$ 的数据，$N\leq1000,K\leq15$。