#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<cmath> #define int long long #define rep(i,a,n) for(register int i=a;i<=n;++i) #define dwn(i,n,a) for(register int i=n;i>=a;--i) #define mod 1000000007 using namespace std; int n,k,m,g[1<<15][3],a[20],b[20],flag1,flag2=1,t[1<<15],ans[20],dp[2][1<<15][3]; char ch[20],str[5]="NOI"; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } void write(int x) { if(!x)return; if(x<0)putchar('-'),x=-x; write(x/10); putchar('0'+x%10); } int get(int s,int c) { rep(i,1,k)a[i]=a[i-1]+(s&1),s>>=1; rep(i,1,k)b[i]=max(max(b[i-1],a[i]),a[i-1]+(str[c]==ch[i])); dwn(i,k,1)s<<=1,s|=(b[i]-b[i-1]); return s; } signed main() { n=read(),k=read(); gets(ch+1); m=1<<k; dp[0][0][0]=1; rep(i,0,m-1) rep(c,0,2) g[i][c]=get(i,c); rep(i,1,n) { memset(dp[flag2],0,sizeof dp[flag2]); rep(j,0,m-1) rep(k,0,2) { int temp; rep(c,0,2) { if(!c)temp=1; else if(c<2)temp=(k==1)?2:0; else temp=(k==2)?3:0; if(temp==3) continue; (dp[flag2][g[j][c]][temp]+=dp[flag1][j][k])%=mod; } } flag1^=1,flag2^=1; } rep(i,0,m-1) { t[i]=t[i>>1]+(i&1); rep(j,0,2)(ans[t[i]]+=dp[flag1][i][j])%=mod; } rep(i,0,k) { if(ans[i])write(ans[i]); else putchar('0'); putchar('\n'); } return 0; }