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
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int main(){
	int n,q,i,j,k,x,nieb,result;
	char c;
	int Z[2];
	int C[2];
	scanf("%d%d",&n,&q);
	char arr[n+1];
	int dp[n+1][3][3];
	scanf("%s",arr);
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			dp[0][i][j]=1;
	dp[0][0][0]=dp[0][1][1]=dp[0][2][2]=0;
	for(k=1;k<=n;k++)
		for(i=0;i<3;i++)
			for(j=0;j<3;j++)
				dp[k][i][j]=(dp[k-1][(i+2)%3][j]+dp[k-1][i][(j+2)%3])%mod;
	Z[0]=Z[1]=C[0]=C[1]=0;
	for(i=0;i<n;i++){
		if(arr[i]=='Z')
			Z[i%2]++;
		if(arr[i]=='C')
			C[i%2]++;
	}
	for(i=0;i<=q;i++){
		nieb=n-Z[0]-Z[1]-C[0]-C[1];
		result=dp[nieb][(Z[0]+Z[1])%3][(C[0]+C[1])%3];
		if(nieb==n){
			if(n%2==1 && n>1)
				result-=2;
		}
		else{
			if(((Z[0]==0 && C[1]==0) || (Z[1]==0 && C[0]==0)) && n>1)
				result-=n%2;
		}
		printf("%d\n",(result+mod)%mod);
		if(i==q)
			continue;
		scanf("%d %c",&x,&c);
		x--;
		if(arr[x]=='Z')
			Z[x%2]--;
		if(arr[x]=='C')
			C[x%2]--;
		arr[x]=c;
		if(arr[x]=='Z')
			Z[x%2]++;
		if(arr[x]=='C')
			C[x%2]++;
	}
	return 0;
}