与 这题 本质相同。
多记录一维当前串与 NOI 匹配到第几位即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1015, M = 20, V = (1 << 15) + 15, mod = 1e9 + 7;
const char ch[] = {'N', 'O', 'I'};
int n, m, pre[M], f[M], g[V][5];
int nxt[5][5];  //填字符后 NOI 匹配到达什么状态
char s[N];
long long dp[2][V][3], ans[M];

int popcnt(int S) {
    int res = 0;
    while (S) res += S & 1, S >>= 1;
    return res;
}

void init() {
    //nxt[i][j]: 已经匹配前 i 位，接下来填 j，匹配位数的变化
    //是连续子区间啊嗷嗷。
    nxt[0][0] = 1, nxt[0][1] = 0, nxt[0][2] = 0;
    nxt[1][0] = 1, nxt[1][1] = 2, nxt[1][2] = 0;
    nxt[2][0] = 1, nxt[2][1] = 0, nxt[2][2] = 3;
}

int main() {
    init();
    scanf("%d%d \n%s", &n, &m, s + 1);
    for (int S = 0; S < (1 << m); S++) {
        for (int i = 0; i <= m; i++) pre[i] = f[i] = 0;
        for (int i = 1; i <= m; i++) {
            pre[i] = pre[i - 1];
            if (S & (1 << i - 1)) pre[i]++;
        }
        for (int k = 0; k < 3; k++) {
            for (int i = 1; i <= m; i++) {
                if (s[i] == ch[k]) f[i] = pre[i - 1] + 1;
                else f[i] = max(pre[i], f[i - 1]);
            }
            int T = 0;
            for (int i = 1; i <= m; i++)
                if (f[i] - f[i - 1]) T |= (1 << i - 1);
            g[S][k] = T;
        }
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int S = 0; S < (1 << m); S++)
            for (int j = 0; j < 3; j++) dp[(i + 1) & 1][S][j] = 0;

        for (int S = 0; S < (1 << m); S++) {
            for (int j = 0; j < 3; j++) {
                if (!dp[i & 1][S][j]) continue;
                dp[i & 1][S][j] %= mod;
                for (int k = 0; k < 3; k++) {
                    if (nxt[j][k] == 3) continue;
                    dp[(i + 1) & 1][ g[S][k] ][ nxt[j][k] ] += dp[i & 1][S][j];
                }
            }
        }
    }
    for (int S = 0; S < (1 << m); S++)
        for (int i = 0; i < 3; i++) ans[popcnt(S)] += dp[n & 1][S][i];
    for (int i = 0; i <= m; i++) printf("%lld\n", ans[i] % mod);
    return 0;
}