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
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const int MAXN = 2e5 + 10;
const ll MOD = 1e9+7;


vector<ll> pow2(MAXN, 0);
vector<ll> dp[3];
int num_n = 0;
int num_z = 0;
int num_c = 0;
int num_zcz = 0;
int num_czc = 1;
int n, q;
string s;

void init(){
	// Evaluate the powers of 2
	pow2[0] = 1;
	for(int i = 1; i < MAXN; i++){
		pow2[i] = (pow2[i-1] * 2) % MOD;
	}

	// dp[i][r] = number of ways we can reach residue r mod 3 using i N's
	dp[0] = vector<ll>(MAXN, 0);
	dp[1] = vector<ll>(MAXN, 0);
	dp[2] = vector<ll>(MAXN, 0);
	dp[0][0] = 1;
	for (int i = 1; i < MAXN; i++){
		dp[0][i] = (dp[1][i-1]+dp[2][i-1])%MOD;
		dp[1][i] = (dp[0][i-1]+dp[2][i-1])%MOD;
		dp[2][i] = (dp[0][i-1]+dp[1][i-1])%MOD;
	}
}

void evaluate_result(){
	ll res = pow2[num_n]-dp[(num_z+2*num_c)%3][num_n];
	if (n%2==1){
		if(num_zcz == 0)
			res--;
		if(num_czc == 0)
			res--;
	}
	res = (res+2*MOD)%MOD;

	cout << res << "\n";
}

void update(int pos, char c){
	if(s[pos]=='N')
		num_n--;
	if(s[pos]=='Z')
		num_z--;
	if(s[pos]=='C')
		num_c--;
	if((s[pos]=='Z' && pos%2==0) || (s[pos]=='C' && pos%2==1))
		num_czc--;
	if((s[pos]=='Z' && pos%2==1) || (s[pos]=='C' && pos%2==0))
		num_zcz--;

	s[pos] = c;

	if(s[pos]=='N')
		num_n++;
	if(s[pos]=='Z')
		num_z++;
	if(s[pos]=='C')
		num_c++;
	if((s[pos]=='Z' && pos%2==0) || (s[pos]=='C' && pos%2==1))
		num_czc++;
	if((s[pos]=='Z' && pos%2==1) || (s[pos]=='C' && pos%2==0))
		num_zcz++;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	init();

	cin >> n >> q;
	cin >> s;

	for (int i = 0; i < s.size(); i++){
		if(s[i]=='N')
			num_n++;
		if(s[i]=='Z')
			num_z++;
		if(s[i]=='C')
			num_c++;
		if((s[i]=='Z' && i%2==0) || (s[i]=='C' && i%2==1))
			num_czc++;
		if((s[i]=='Z' && i%2==1) || (s[i]=='C' && i%2==0))
			num_zcz++;
	}

	evaluate_result();

		
	while(q--){
		int pos;
		char c;
		cin >> pos >> c;
		pos--;
		update(pos, c);
		evaluate_result();
	}

}