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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <algorithm>
using namespace std;
using ll=long long;
const int M=1000000007, C=500001;

std::pair <ll, ll> Euclid (ll a, ll b){
	ll x1=0, x2=1, y1=1, y2=0, q=a/b, r=a-q*b, x, y, wynn;
	x=1, y=y2-(q-1)*y1;
	while (r!=0){
		a=b, b=r;
		x=x2-q*x1, x2=x1, x1=x;
		y=y2-q*y1, y2=y1, y1=y;
		wynn=r, q=a/b, r=a-q*b;
	}
	return std::make_pair (x,y);
}
ll invert(ll a, ll M){
	ll x=Euclid(a, M).first;
	if (x<0) return x+M;
	return x;
}

ll inverted_2 = invert(2, M);
ll divided_cosine(ll n, ll mod){
	ll proper_n = n;
	if (mod == 1) proper_n -= 2;
	if (mod == 2) proper_n -= 4;
	proper_n = (proper_n + 6) % 6;

	if (proper_n == 0) return 1;
	if (proper_n == 1 || proper_n == 5) return inverted_2;
	if (proper_n == 2 || proper_n == 4) return -inverted_2;
	return -1;
}

int chain_paired[C];
ll pw_2[C];
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	pw_2[0] = 1;
	for (int i=1; i<C; i++) pw_2[i] = (pw_2[i-1]*2)%M;

	int n, q;
	ll res = 0;
	string chain;

	cin >> n >> q;
	cin >> chain;
	int amount_of_ns = 0;
	int pairs = 0, free_variables = 0;
	ll summa=0, odd_C=0, even_C=0, odd_Z=0, even_Z=0;


	for (int i=0; i<n; i++){
		if (i%2 == 0){
			if (chain[i] == 'C') even_C++;
			if (chain[i] == 'Z') even_Z++;
		}
		if (i%2 == 1){
			if (chain[i] == 'C') odd_C++;
			if (chain[i] == 'Z') odd_Z++;
		}

		if (chain[i] == 'N') amount_of_ns++;
		if (chain[i] == 'N' || chain[i] =='C') summa++;
		if (chain[i] == 'Z') summa+=2;
	}

	for (int i=0; i<n-1; i++){
		if (chain[i] != 'N' && chain[i] == chain[i+1]){
			chain_paired[i] = 1;
			pairs++;
		}
	}

	int pos;
	char element;
	ll inverted_3 = invert(3, M);

	if (n != 1 && pairs == 0 && n%2 == 1 && amount_of_ns == n) free_variables = 2;
	else if (n != 1 && pairs == 0 && n%2 == 1 && ((odd_Z == 0 && even_C == 0) || (odd_C == 0 && even_Z == 0))) free_variables = 1;
	else free_variables = 0;


	ll dissonance = 3-(summa%3);
	ll parting = 2 * divided_cosine(amount_of_ns, dissonance);

	ll partial_antires = (inverted_3 * (pw_2[amount_of_ns] + parting))%M; //Dodać n, n-2, n-4
	//cout << "Ares: " << partial_antires << endl;
	res = (pw_2[amount_of_ns] - partial_antires - free_variables)%M;
	if (res < 0) res += M;

	// cout << pairs << ' ' << free_variables << ' ' << amount_of_ns << ' ' << summa << endl;
	cout << res << endl;
	while (q--){
		cin >> pos >> element;
		pos--;

		if (pos%2 == 0){
			if (chain[pos] == 'C') even_C--;
			if (chain[pos] == 'Z') even_Z--;

			if (element == 'C') even_C++;
			if (element == 'Z') even_Z++;
		}
		if (pos%2 == 1){
			if (chain[pos] == 'C') odd_C--;
			if (chain[pos] == 'Z') odd_Z--;

			if (element == 'C') odd_C++;
			if (element == 'Z') odd_Z++;
		}

		if (chain[pos] == 'N') amount_of_ns--;
		if (element == 'N') amount_of_ns++;

		if (chain[pos] == 'N' || chain[pos] == 'C') summa--;
		if (chain[pos] == 'Z') summa -= 2;

		if (element == 'N' || element == 'C') summa++;
		if (element == 'Z') summa += 2;

		chain[pos] = element;

		pairs = pairs - chain_paired[pos] - ((pos>0)?chain_paired[pos-1]:0);
		chain_paired[pos] = 0;
		if (pos > 0) chain_paired[pos-1] = 0;

		if (pos<n-1 && chain[pos] == chain[pos+1] && chain[pos] != 'N'){
			chain_paired[pos] = 1;
		       	pairs++;
		}
		if (pos>0 && chain[pos] == chain[pos-1] && chain[pos] != 'N'){
		       chain_paired[pos-1] = 1;
	       	       pairs++;
		}
		if (n!= 1 && pairs == 0 && n%2 == 1 && amount_of_ns == n) free_variables = 2;
		else if (n != 1 && pairs == 0 && n%2 == 1 && ((odd_Z == 0 && even_C == 0) || (odd_C == 0 && even_Z == 0))) free_variables = 1;
		else free_variables = 0;

		// cout << pairs << ' ' << free_variables << ' ' << amount_of_ns << ' ' << summa << endl;

		ll dissonance = 3-(summa%3);
		ll parting = 2 * divided_cosine(amount_of_ns, dissonance);

		ll partial_antires = (inverted_3 * (pw_2[amount_of_ns] + parting))%M; //Dodać n, n-2, n-4
		res = (pw_2[amount_of_ns] - partial_antires - free_variables)%M;
		if (res < 0) res += M;

		cout << res << endl;
	}

return 0;}