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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define gc getchar_unlocked
using namespace std;
typedef long long ll;
constexpr ll mod = 1000000007ll;

int dod(int a, int b){
	return a+b<mod ? a+b : a+b-mod;
}
int ode(int a, int b){
	return a-b>=0 ? a-b : a-b+mod;
}
int ilo(int a, int b){
	return (a*ll(b))%mod;
}

void wczytaj(int &a){
	int c = gc();
	while(c < '0' || c > '9') c = gc();
	for(a = 0; c >= '0' && c <= '9'; c = gc()) a = 10*a+c-'0';
}

void znak(int &a){
	a = gc();
	while(a != 'C' && a != 'N') a = gc();
}

void solve(){
	int n, m, k;
	wczytaj(n), wczytaj(m), wczytaj(k);
	
	int mnoznik = 1<<(m-1);
	int zakres = mnoznik*m*((n-k+2)/2);
	int rozmiar = 2*zakres+1;
	auto ewaluacja = [&](vector<int> vec){
		int znak = 1;
		if(!vec[0]){
			znak = -1;
			for(int &i : vec) i = !i;
		}
		int zmiana = -1;
		REP(i, m-1) if(vec[i] != vec[i+1]){zmiana = i; break;}
		if(zmiana < 0) return znak*mnoznik*m;
		int ret = zmiana*mnoznik;
		int tmp = mnoznik>>1;
		FOR(i, zmiana+2, m-1){
			if(vec[i]) ret += tmp;
			tmp >>= 1;
		}
		ret += tmp;
		return znak*ret;
	};
	
	int sumka = 0;
	REP(i, k){
		vector<int> vec(m);
		REP(j, m) znak(vec[j]), vec[j] = vec[j]=='N' ? 1 : 0;
		sumka += ewaluacja(vec);
	}
	
	vector<int> teraz(rozmiar, 0);
	++teraz[zakres];
	REP(xd, n-k+1){
		printf("%d ", teraz[sumka+zakres]);
		vector<int> nowy(rozmiar, 0);
		auto przemnoz = [&](int poc, int dl, int skok){
			vector<int> suma_pref = teraz;
			FOR(i, skok, rozmiar-1) suma_pref[i] = dod(suma_pref[i], suma_pref[i-skok]);
			FOR(i, poc, rozmiar-1) nowy[i] = dod(nowy[i], suma_pref[i-poc]);
			FOR(i, poc+dl*skok, rozmiar-1) nowy[i] = ode(nowy[i], suma_pref[i-poc-dl*skok]);
		};
		FOR(i, 1, m){
			if(i == m) przemnoz(m*mnoznik, 1, 69);
			else przemnoz(mnoznik*(i-1)+(1<<(i-1)), 1<<(m-1-i), 1<<i);
		}
		REP(i, rozmiar) teraz[i] = dod(nowy[i], nowy[rozmiar-1-i]);
	}
}

int main(){
	solve();
	return 0;
}