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
#include<bits/stdc++.h>
using namespace std;
using lld = long long;

const int mod = 1e9+7;
const int MAXN = 2e5;

int P2[MAXN+1];
int P[3][MAXN+1];

int cnt_c = 0, cnt_z = 0, cnt_n = 0;
int czc = 0, zcz = 0;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	P2[0] = 1;
	P[0][0] = 1;
	P[1][0] = 0;
	P[2][0] = 0;
	for(int i=1;i<=MAXN;i++) {
		P[0][i] = (P[1][i-1] + P[2][i-1]) % mod;
		P[1][i] = (P[0][i-1] + P[2][i-1]) % mod;
		P[2][i] = (P[0][i-1] + P[1][i-1]) % mod;
		P2[i] = (2 * P2[i-1]) % mod;
	}

	int n,q;
	cin >> n >> q;

	string s;
	cin >> s;

	auto f = [&](int i, int sgn) {
		if(s[i] == 'C')
			cnt_c += sgn, czc += (i%2 == 0 ? sgn : 0), zcz += (i%2 == 1 ? sgn : 0);
		else if(s[i] == 'Z')
			cnt_z += sgn, czc += (i%2 == 0 ? 0 : sgn), zcz += (i%2 == 1 ? 0 : sgn);
		else if(s[i] == 'N')
			cnt_n += sgn, czc += sgn, zcz += sgn;
	};

	auto add = [&](int i) { f(i, 1); };
	auto rem = [&](int i) { f(i, -1); };

	auto solve = [&]() {
		int md = (cnt_c - cnt_z + 3*n) % 3;
		if(md != 0) md = 3-md;

		lld res = (lld) P2[cnt_n] - (lld) P[md][cnt_n] + 2ll*mod;
		if(czc == n && n%2 != 0) res--;
		if(zcz == n && 2*(n%2) != 0) res--;
		return res % mod;
	};

	for(int i=0;i<n;i++)
		add(i);

	cout << solve() << "\n";

	while(q--) {
		int i;
		char c;
		cin >> i >> c, i--;

		rem(i);
		s[i] = c;
		add(i);

		cout << solve() << "\n";
	}

	return 0;
}