Xiao Dou participated in a carnival at NOI, where completing each event earns a badge. Badges only consist of the letters N, O, and I. At the carnival, he collected a string of $K$ badges. The rules for prizes are based on the length of the Longest Common Subsequence (LCS) between the collected string and the prize string. It is known that the length of the prize string is $N$, and the prize string will not contain the three consecutive letters NOI. That is, the prize string will not contain the substring NOI. Now, Xiao Dou wants to know how many different valid prize strings correspond to each possible prize level (where the prize level is defined by the length of the LCS).

Input

The first line contains two integers $N$ and $K$, representing the length of the prize string and the length of the string collected by Xiao Dou, respectively ($N \le 1000, K \le 15$).

The second line contains a string of length $K$, representing the badges Xiao Dou collected.

Output

The output consists of $K+1$ lines. The $i$-th line represents the number of valid prize strings whose LCS length with the collected string is $i-1$. Since this number can be very large, output the result modulo $10^9 + 7$.

Constraints

• For 10% of the data, $N \le 10, K \le 10$.
• For 30% of the data, $N \le 100, K \le 4$.
• For 100% of the data, $N \le 1000, K \le 15$.

Examples

Input 1

3 2
NO

Output 1

1
19
6

Note

• Prize strings with LCS length 0: III;
• Prize strings with LCS length 2: NON, NNO, NOO, ONO, INO, NIO;
• Excluding NOI, the remaining $19 (26-6-1)$ types have an LCS length of 1.