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
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int mod = 1e9 + 7, nax = 200 * 1000 + 10, inv3 = 333333336;
int n, q;
string s;
int cnt[2][2];
int pt2[nax];

int computeBin(int x, int r) {
	int w = pt2[x];
	if (r == 0) {
		if (x % 6 == 0) w += 2;
		else if (x % 6 == 1 || x % 6 == 5) w += 1;
		else if (x % 6 == 2 || x % 6 == 4) w -= 1;
		else w -= 2;
	} else if (r == 1) {
		if (x % 6 == 2) w += 2;
		else if (x % 6 == 3 || x % 6 == 1) w += 1;
		else if (x % 6 == 0 || x % 6 == 4) w -= 1;
		else w -= 2;
	} else {
		if (x % 6 == 4) w += 2;
		else if (x % 6 == 5 || x % 6 == 3) w += 1;
		else if (x % 6 == 0 || x % 6 == 2) w -= 1;
		else w -= 2;
	}
	w = ((ll)w * inv3) % mod;
	return w;
}

int ask() {
	int decide = 0, ones = 0;
	for (int i : {0, 1}) {
		for (int j : {0, 1}) {
			decide += cnt[i][j];
		}
		ones += cnt[i][1];
	}
	decide = n - decide;
	int rem = (-n-ones) % 3;
	if (rem < 0) rem += 3;
	// rem - forbiiden remainder
	int ans = (pt2[decide] - computeBin(decide, rem)) % mod;
	// need to also substract cases when i am alternating
	
	if (n % 2 == 1 && n > 1) {
		// case 1: pattern (0,1,0,1,0)

		if (cnt[0][1] == 0 && cnt[1][0] == 0) {
			ans--;
		}
		
		//case 2: pattern (1,0,1,0,1)
		if (cnt[1][1] == 0 && cnt[0][0] == 0) {
			ans--;
		}
	}

	if (ans < 0) ans += mod;
	return ans;
}

void upd(int x, int dx) {
	if (s[x] == 'C') cnt[x & 1][0] += dx;
	if (s[x] == 'Z') cnt[x & 1][1] += dx;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> s;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'C') cnt[i & 1][0]++;
		else if (s[i] == 'Z') cnt[i & 1][1]++;
	}
	pt2[0] = 1;
	for (int i = 1; i <= n; ++i) pt2[i] = ((ll)pt2[i - 1] * 2) % mod;
	cout << ask() << "\n";
	for (int i = 0; i < q; ++i) {
		int x;
		char c;
		cin >> x >> c;
		x--;
		upd(x, -1);
		s[x] = c;
		upd(x, 1);
		cout << ask() << "\n";
	}
}