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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1'000'000'007;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, q;
	string s;
	cin >> n >> q >> s;
	
	int C = 0, Z = 0, N = 0;
	vector<int> parity_C(2), parity_Z(2);
	for (int i = 0; i < n; i++) {
		if (s[i] == 'C') {
			C++;
			parity_C[i % 2]++;
		}
		else if (s[i] == 'Z') {
			Z++;
			parity_Z[i % 2]++;
		}
		else {
			N++;
		}
	}
	
	vector<vector<long long>> sum_ways(n + 1, vector<long long>(3));
	sum_ways[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			sum_ways[i][j] = (sum_ways[i - 1][j] + sum_ways[i - 1][(j + 2) % 3]) % MOD;
		}
	}
	
	auto get_ways = [&]() {
		long long result = 0;
		
		for (int j = 0; j <= min(2, N); j++) {
			int diff = ((C + j) - (Z + (N - j))) % 3;
			if (diff < 0) {
				diff += 3;
			}
			if (diff != 0) {
				result = (result + sum_ways[N][j]) % MOD;
			}
		}
		
		if (n > 1 && n % 2 == 1) {
			if (parity_C[0] == C && parity_Z[1] == Z) {
				result = (result + MOD - 1) % MOD;
			}
			if (parity_Z[0] == Z && parity_C[1] == C) {
				result = (result + MOD - 1) % MOD;
			}
		}
		
		return result;
	};
	
	cout << get_ways() << '\n';
	while (q--) {
		int i;
		char x;
		cin >> i >> x;
		i--;
		
		if (s[i] == 'C') {
			C--;
			parity_C[i % 2]--;
		}
		else if (s[i] == 'Z') {
			Z--;
			parity_Z[i % 2]--;
		}
		else {
			N--;
		}
		
		s[i] = x;
		
		if (s[i] == 'C') {
			C++;
			parity_C[i % 2]++;
		}
		else if (s[i] == 'Z') {
			Z++;
			parity_Z[i % 2]++;
		}
		else {
			N++;
		}
		
		cout << get_ways() << '\n';
	}
	
	return 0;
}