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
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)
#define STR(n,x) char x[n]; scanf("%s", x)
#define LINE(n,x) char x[n]; fgets(x, n, stdin)

const int mod = 1000000007;
int p[200001][3];

int main() {
	INT(n);
	INT(q);
	scanf("\n");
	LINE(200010, a);
	p[0][0] = 1;
	p[0][1] = p[0][2] = 0;
	REP(i,n) REP(j,3) p[i + 1][j] = (p[i][(j + 1) % 3] + p[i][(j + 2) % 3]) % mod;
	int c[2], z[2], nn = 0, s = 0;
	REP(j,2) c[j] = z[j] = 0;
	REP(i,n) switch (a[i]) {
		case 'C': {
			++c[i & 1];
			s = (s + 1) % 3;
			break;
		}
		case 'Z': {
			++z[i & 1];
			s = (s + 2) % 3;
			break;
		}
		default:
			++nn;
			break;
	}
	int r = 0;
	REP(j,3) if ((j + s) % 3)
		r = (r + p[nn][j]) % mod;
	if (n & 1) {
		if (!c[0] && !z[1]) r = (r + mod - 1) % mod;
		if (!c[1] && !z[0]) r = (r + mod - 1) % mod;
	}
	printf("%d\n", r);
	REP(qq,q) {
		INT(k);
		--k;
		STR(2,x);
		switch (a[k]) {
			case 'C': {
				--c[k & 1];
				s = (s + 2) % 3;
				break;
			}
			case 'Z': {
				--z[k & 1];
				s = (s + 1) % 3;
				break;
			}
			default:
				--nn;
				break;
		}
		a[k] = x[0];
		switch (a[k]) {
			case 'C': {
				++c[k & 1];
				s = (s + 1) % 3;
				break;
			}
			case 'Z': {
				++z[k & 1];
				s = (s + 2) % 3;
				break;
			}
			default:
				++nn;
				break;
		}
		r = 0;
		REP(j,3) if ((j + s) % 3)
			r = (r + p[nn][j]) % mod;
		if (n & 1) {
			if (!c[0] && !z[1]) r = (r + mod - 1) % mod;
			if (!c[1] && !z[0]) r = (r + mod - 1) % mod;
		}
		printf("%d\n", r);
	}
}