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
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int K = 3;
const int MOD = 1e9+7;
typedef long long ll;
ll dp[N][K],pr[N];
int A[N];
int gi(char ch){
	if (ch=='N'){
		return 0;
	}
	else{
		return 1+(ch=='Z');
	}
}
void solve(){
	int n,q;
	cin>>n>>q;
	int free = 0,cnt[2] = {0,0};
	int sum = 0;
	for(int i = 1;i<=n;i+=1){
		char sym;
		cin>>sym;
		A[i] = gi(sym);
		if (A[i]==0){
			free += 1;
		}
		else{
			cnt[(A[i]-1+i)%2] += 1;
			sum += A[i]-1;
		}
	}
	for(int qe = 0;qe<=q;qe+=1){
		char sym;
		int pos;
		if (qe>0){
			cin>>pos>>sym;
			if (A[pos]==0){
				free -= 1;
			}
			else{
				cnt[(A[pos]-1+pos)%2] -= 1;
				sum -= A[pos] - 1;
			}
			A[pos] = gi(sym);
			if (A[pos]==0){
				free += 1;
			}
			else{
				cnt[(A[pos]-1+pos)%2] += 1;
				sum += A[pos] - 1;
			}
		}
		if (n==1){
			cout<<pr[free]<<endl;
			continue;
		}
		if (n%2==0){
			int dif = (sum*2-(n-free))%3;
			if (dif<0){
				dif += 3;
			}
			cout<<(pr[free]-dp[free][(3-dif)%3]+MOD)%MOD<<endl;
	//		cout<<"GDB "<<free<<' '<<pr[free]<<' '<<dif<<' '<<sum<<endl;
		}
		else{
			int dif = (sum*2-(n-free))%3;
			if (dif<0){
				dif += 3;
			}
			cout<<(pr[free]-dp[free][(3-dif)%3]-(cnt[0]==0)-(cnt[1]==0)+MOD)%MOD<<endl;
		}
	}
}
signed main(){
	dp[0][0] = 1;
	pr[0] = 1;
	for(int i = 1;i<N;i+=1){
		pr[i] = pr[i-1]*2%MOD;
		for(int j = 0;j<K;j+=1){
			dp[i][(j+2)%K] += dp[i-1][j];
			dp[i][(j+1)%K] += dp[i-1][j];
		}
		for(int j = 0;j<K;j+=1){
			dp[i][j] %= MOD;
		}
	}
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tt = 1;
	while(tt--){
		solve();
	}
}