P4590 [TJOI2018] 游园会

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

无

无

### 样例解释 最长公共子序列长度为 $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$。