题目描述

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

输入格式

第一行两个数 $N$，$K$ 分别代表兑奖串的长度，小豆收集的奖章串的长度。
第二行一共 $K$ 个字符，表示小豆得到的奖章串。

输出格式

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

样例

输入

3 2  
NO  

输出

1  
19  
6  

说明
最长公共子序列长度为 $0$ 的串有：$III$；
最长公共子序列长度为 $2$ 的串有：$NON$、$NNO$、$NOO$、$ONO$、$INO$、$NIO$；
除去 $NOI$（不合法），余下的 $19$（$26-6-1$）种为最长公共子序列长度为 $1$。

数据范围与提示

对于 $10\%$ 的数据，有 $N \leq 10$，$K \leq 10$；
对于 $30\%$ 的数据，有 $N \leq 100$，$K \leq 4$；
对于 $100\%$ 的数据，有 $N \leq 1000$，$K \leq 15$。