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
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<array<int, 3>> f(n + 1);
	vector<int> g(n + 1);
	f[0][0] = g[0] = 1;
	for(int i = 1; i <= n; i ++) {
		f[i][0] = (f[i - 1][0] + f[i - 1][2]) % mod;
		f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
		f[i][2] = (f[i - 1][2] + f[i - 1][1]) % mod;
		g[i] = (1ll * f[i][0] + f[i][1] + f[i][2]) % mod;
	}
	string str;
	cin >> str;
	int cnt1 = 0, cnt2 = 0, cntN = 0, cntC = 0, cntZ = 0;
	string w = "ZC";
	auto upd = [&] (int p, int k) {
		cnt1 += (str[p] == 'N' || str[p] == w[p & 1]) * k;
		cnt2 += (str[p] == 'N' || str[p] == w[1 + p & 1]) * k;
		cntN += (str[p] == 'N') * k;
		cntC += (str[p] == 'C') * k;
		cntZ += (str[p] == 'Z') * k;
	};
	for(int i = 0; i < n; i ++) upd(i, 1);
	auto ask = [&] {
		int res = (3 - ((cntC + cntN - cntZ) % 3 + 3) % 3) % 3;
		return (g[cntN] - f[cntN][res] - (cnt1 == n && n % 2 == 1 && n > 1) - (cnt2 == n && n % 2 == 1 && n > 1) + mod) % mod;
	};
	cout << ask() << '\n';
	for(int i = 0; i < q; i ++) {
		int p; char c;
		cin >> p >> c; p --;
		upd(p, -1);
		str[p] = c;
		upd(p, 1);
		cout << ask() << '\n';
	}
	return 0;
}