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
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; i >= a; i--)
#define cat(x) cout << #x << ": " << x << endl

using namespace std;
using ll = long long;

const int N = 200200;
const int P = 1e9 + 7;

int n, q, dp[N][3], cnt[2][2];
char s[N];

void update(int p, char v, int c) {
	if (v == 'C') cnt[p % 2][0] += c;
	if (v == 'Z') cnt[p % 2][1] += c;
}

void answer() {
	int cnt0 = cnt[0][0] + cnt[1][0];
	int cnt1 = cnt[0][1] + cnt[1][1];
	int cntq = n - cnt0 - cnt1;
	int w = 2 * (cnt0 + cntq - cnt1 % 3 + 3) % 3;
	int res = (dp[cntq][(w + 1) % 3] + dp[cntq][(w + 2) % 3]) % P;
	if (n % 2 == 1 && n > 1) {
		res = (res - (cnt[0][0] == 0 && cnt[1][1] == 0) + P) % P;
		res = (res - (cnt[0][1] == 0 && cnt[1][0] == 0) + P) % P;
	}
	cout << res << "\n";
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> q;
	rep(i, 1, n) {
		cin >> s[i];
		update(i, s[i], 1);
	}

	dp[0][0] = 1;
	rep(i, 1, n) {
		rep(r, 0, 2) {
			rep(x, 0, 1) {
				dp[i][r] = (dp[i][r] + dp[i - 1][(r - x + 3) % 3]) % P;
			}
		}
	}

	answer();
	while (q--) {
		int p;
		cin >> p;
		update(p, s[p], -1);
		cin >> s[p];
		update(p, s[p], +1);
		answer();
	}

	return 0;
}