BZPRO

#5336. [TJOI2018]party

内存限制：256 MiB 时间限制：60 Sec
提交 提交记录 讨论

题目描述

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

输入格式

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

输出格式

一共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。

数据范围与提示

BZPRO Powered by Remmina.
Github Repository