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
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>

using namespace std;

const int maxn=2e5; 

const int mod=1e9+7;
int has[2][2]; 
int cnt[3]={}; 

int add(int x,int y) {
	return (x+=y)>=mod?x-mod:x; 
}
int fpw(int x,int k,int p) {
	int ret=1;
	while (k) {
		if (k&1) ret=1ll*ret*x%p;
		x=1ll*x*x%p; k>>=1; 
	}
	return ret; 
}
int f[maxn+5][3]; 
int n,q;
char s[maxn+5];
int a[maxn+5]; 
void calc() {
	//cout<<"**"<<cnt[0]<<' '<<cnt[1]<<'\n'; 
	int ans=0; 
	for (int j=0;j<3;j++) {
		int t=(j+cnt[0]-cnt[1])%3;
		t=(t+3)%3; 
		if (t!=0) ans=add(ans,f[cnt[2]][j]); 
	}
	if (n%2==1) {
		if (has[0][1]==0 && has[1][0]==0) ans--;
		if (has[0][0]==0 && has[1][1]==0) ans--; 
	}
	cout<<ans<<'\n'; 
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin>>n>>q;
	cin>>(s+1); 
	f[0][0]=1;
	for (int i=1;i<=maxn;i++) {
		for (int j=0;j<3;j++) {
			for (int k=0;k<2;k++) {
				int o=(k==0?1:2); 
				f[i][(j+o)%3]=add(f[i][(j+o)%3],f[i-1][j]); 
			}
		}
	}
	for (int i=1;i<=n;i++) {
		if (s[i]=='Z') a[i]=0;
		else if (s[i]=='C') a[i]=1; 
		else a[i]=2; 
		if (a[i]<=1) has[i%2][a[i]]++; 
		cnt[a[i]]++; 
	}
	calc(); 
	for (int i=1;i<=q;i++) {
		int p; char c; int x;
		cin>>p>>c;
		if (c=='Z') x=0; else if (c=='C') x=1; else x=2; 
		cnt[a[p]]--;
		if (a[p]<=1)
			has[p%2][a[p]]--;
		a[p]=x;  
		cnt[a[p]]++;
		if (a[p]<=1)
			has[p%2][a[p]]++;
		calc(); 
	}
	return 0;
}