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
#include <cstdio>

const int md = 1000000007;

inline int add(int a, int b) {
	return a + b < md ? a + b : a + b - md;
}
inline int sub(int a, int b) {
	return a - b < 0 ? a - b + md : a - b;
}

int z3(int x) {
	if (x >= 3) x -= 3;
	if (x < 0) x += 3;
	return x;
}

const int N = 200005;
int n, q, d[N][3], suma[2], licz, roz;
char s[N];

void uzyc(int i, int k) {
	licz += (s[i] == 'N') * k;
	suma[0] += (i & 1 && s[i] == 'C' || i & 1 ^ 1 && s[i] == 'Z') * k;
	suma[1] += (i & 1 && s[i] == 'Z' || i & 1 ^ 1 && s[i] == 'C') * k;
	if (s[i] == 'C') roz += k;
	if (s[i] == 'Z') roz -= k;
	roz = z3(roz);
}

int policz() {
	int ans = 0;
	for (int i = 0; i < 3; ++i) if (z3(i + roz)) ans = add(ans, d[licz][i]);
	if (n & 1 && n > 1) {
		ans = sub(ans, !suma[0]);
		ans = sub(ans, !suma[1]);
	}
	return ans;
}

int main() {
	scanf("%d%d%s", &n, &q, s);
	for (int i = 0; i < n; ++i) uzyc(i, 1);
	d[0][0] = 1;
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j < 3; ++j) 
			for (int k = 0; k < 3; ++k) 
				d[i][k] = add(d[i][k], d[i - 1][z3(k - j)]);
	printf("%d\n", policz());
	while (q--) {
		int ind;
		char c;
		scanf("%d %c", &ind, &c);
		--ind;
		uzyc(ind, -1);
		s[ind] =c;
		uzyc(ind, 1);
		printf("%d\n", policz());
	}
	return 0;
}