1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll n, m, k;
  cin >> n >> m >> k;
  ll sum=0;
  rep(i, k) {
    string s;
    cin >> s;
    ll akt=1ll<<(m-1);
    bool ok=true;
    rep(j, m) {
      if(!ok) akt/=2;
      if(s[j]=='C') sum+=akt; else sum-=akt;
      if(j+1<m && s[j]!=s[j+1]) ok=false;
    }
  }
  cout << (sum==0?1:0) << " " << (n==k?"\n":"");
  if(n==k) return 0;
  ll zero=(1ll<<(m-1))*m*n+10;
  vector<ll>dp(2*zero);
  dp[zero]=1;
  rep(xd, n-k) {
    vector<ll>dp2(2*zero);
    for(ll j=1; j<m; ++j) {
      vector<ll>dodaj(2*zero);
      ll p=0, krok=1;
      rep(i, m-j-1) {
        p+=1ll<<(m-i-3);
        krok=1ll<<(m-i-2);
      }
      rep(i, 2*zero) if(dp[i]) {
        ll d=i+(1ll<<(m-1))*j-(1ll<<(m-2));
        d-=p;
        dodaj[d]=(dodaj[d]+dp[i])%MOD;
        d+=2*p+krok;
        if(d<dodaj.size()) dodaj[d]=(dodaj[d]-dp[i]+MOD)%MOD;
        d=i-(1ll<<(m-1))*j+(1ll<<(m-2));
        d-=p;
        dodaj[d]=(dodaj[d]+dp[i])%MOD;
        d+=2*p+krok;
        if(d<dodaj.size()) dodaj[d]=(dodaj[d]-dp[i]+MOD)%MOD;
      }
      rep(i, 2*zero) {
        if(i+krok<dodaj.size()) dodaj[i+krok]=(dodaj[i+krok]+dodaj[i])%MOD;
        dp2[i]=(dp2[i]+dodaj[i])%MOD;
      }
    }
    rep(i, 2*zero) {
      ll a=i+m*(1ll<<(m-1));
      if(a<dp2.size()) dp2[a]=(dp2[a]+dp[i])%MOD;
      a=i-m*(1ll<<(m-1));
      if(a>=0) dp2[a]=(dp2[a]+dp[i]+MOD)%MOD;
    }
    dp=dp2;
    cout << dp[zero-sum] << " ";
  }
  cout << '\n';
}