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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>

//er1 CZCZ
//er2 ZCZC

#define MD 1000000007

int main(){
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int n, q, er1, er2, z = 0, c = 0, r, b;
	std::cin >> n >> q;
	char* t = new char[n];
	std::cin >> t;
	for(int i = 0; i < n; i++){
		if(t[i] == 'C'){
			if(i%2==1){
				er1++;
			}else{
				er2++;
			}
			c++;
		}
		if(t[i] == 'Z'){
			if(i%2==0){
				er1++;
			}else{
				er2++;
			}
			z++;
		}
	}
	
	int *S0, *S1, *S2;
	S0 = new int[n+1];
	S1 = new int[n+1];
	S2 = new int[n+1];
	S0[0] = 1;
	S1[0] = 0;
	S2[0] = 0;
	
	for(int i = 1; i <= n; i++){
		S0[i] = S0[i-1] + S2[i-1];
		S1[i] = S1[i-1] + S0[i-1];
		S2[i] = S2[i-1] + S1[i-1];
		S0[i] %= MD;
		S1[i] %= MD;
		S2[i] %= MD;
	}
	
	int pos;
	char g;
	long long sum;
	int tmp;
	bool r1 = true, r2 = true;
	tmp = (n+1)/2 + (n/2)*2;
	tmp %= 3;
	if(tmp == 0) r1 = false;
	tmp = ((n+1)/2)*2 + n/2;
	tmp %= 3;
	if(tmp == 0) r2 = false;
	
	for(int i = 0; i <= q; i++){
		
		r = (n + z) % 3;
		b = n - c - z;
		r = (3-r)%3;
		
		sum = S0[b] + S1[b] + S2[b];
		if(r == 0) sum -= S0[b];
		if(r == 1) sum -= S1[b];
		if(r == 2) sum -= S2[b];
		if(er1 == 0 && r1) sum--;
		if(er2 == 0 && r2) sum--;
		
		sum %= MD;
		
		std::cout << sum << "\n";
		
		if(i == q) break;
		std::cin >> pos >> g;
		pos--;
		if(t[pos] == 'Z'){
			z--;
			if(pos%2==0){
				er1--;
			}else{
				er2--;
			}
		}
		if(t[pos] == 'C'){
			c--;
			if(pos%2==1){
				er1--;
			}else{
				er2--;
			}
		}
		
		if(g == 'Z'){
			z++;
			if(pos%2==0){
				er1++;
			}else{
				er2++;
			}
		}
		if(g == 'C'){
			c++;
			if(pos%2==1){
				er1++;
			}else{
				er2++;
			}
		}
		t[pos] = g;
	}
	return 0;
}