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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5 + 5;
const int mod = 1e9 + 7;

char s[MAXN];

int main(void)
{
	int n,Q;
	scanf("%d%d%s",&n,&Q,s+1);
	
	static int f[MAXN][3];
	f[0][0] = 1;
	for(int i=1; i<=n; ++i)
		for(int j=0; j<3; ++j)
			f[i][j] = (f[i-1][(j-1+3)%3] + f[i-1][(j-2+3)%3]) %mod;
	
	static int cnt[2][4];
	auto upd = [&] (int i,int k)
	{
		int x = s[i] == 'C'? 1: s[i] == 'Z'? 2: 3;
		cnt[i%2][x] += k;
	};
	auto query = [&] (void) -> int
	{
		int cnt3 = cnt[0][3] + cnt[1][3];
		int sumoth = ((cnt[0][1] + cnt[1][1]) * 1 + (cnt[0][2] + cnt[1][2]) * 2) % 3;
		
		int ans = 0;
		for(int i=0; i<3; ++i)
			if((sumoth + i) % 3 != 0)
				ans = (ans + f[cnt3][i]) %mod;
		
		if(n % 2 != 0 && n > 1)
		{
			if(cnt[0][1] == 0 && cnt[1][2] == 0)
				ans = (ans - 1 + mod) %mod;
			if(cnt[0][2] == 0 && cnt[1][1] == 0)
				ans = (ans - 1 + mod) %mod;
		}
		
		return ans;
	};
	
	for(int i=1; i<=n; ++i)
		upd(i, 1);
	
	printf("%d\n",query());
	while(Q--)
	{
		int pos;
		static char op[10];
		scanf("%d%s",&pos,op);
		
		upd(pos, -1);
		s[pos] = *op;
		upd(pos, 1);
		
		printf("%d\n",query());
	}
	return 0;
}