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

using namespace std;

const int mod = 1e9 + 7;
int n, q;
string s;
vector <int> dp[3];

void pre(){
	for(int i=0; i<3; i++)dp[i].resize(n+3);
	dp[0][0] = 1;
	dp[1][0] = 0;
	dp[2][0] = 0;
	for(int i=1; i<=n; i++){
		dp[0][i] = dp[1][i-1] + dp[2][i-1];
		dp[1][i] = dp[2][i-1] + dp[0][i-1];
		dp[2][i] = dp[0][i-1] + dp[1][i-1];
		for(int j=0; j<3; j++)dp[j][i]%=mod;
	}
}

void wczytaj(){
	cin>>n>>q;
	cin>>s;
	pre();
}
int count_blue = 0, count_red = 0, count_green = 0;
int count_red_even = 0, count_green_even = 0;

int pow(int pod, int w){
	if(w == 0)return 1;
	if(w == 1)return pod;
	if(w%2==1)return (pod*pow(pod, w-1))%mod;
	int p = pow(pod, w/2);
	return (p*p)%mod;
}

int liczpoprawke(){
	if(s.size()%2==0)return 0;
	int res = 0;
	if(count_green_even == count_green && count_red_even == 0)res++;
	if(count_red_even == count_red && count_green_even == 0)res++;
	return res;
}

int anwser(){
    if(s.size() == 1){
        if(s[0] == 'N')return 2;
        return 1;
    }
	//cout<<count_red<<" "<<count_green<<" "<<count_blue<<" "<<count_green_even<<" "<<count_red_even<<endl;
	int all = pow(2ll, count_blue);
	int aktreszta = count_red + 2*count_green; aktreszta%=3;
	int poprawka = liczpoprawke();
	/*cout<<"wypisanie: ";
	cout<<all<<" "<<aktreszta<<" "<<poprawka<<endl;
	cout<<(3 - aktreszta )%3<<' '<<count_blue<<' '<<dp[ ( 3 - aktreszta )%3 ][count_blue]<<endl;*/
      //cout<< all<< " " <<dp[ ( 3 - aktreszta )%3 ][count_blue]<< " "<<poprawka<<" "<< mod<<endl;
      //cout<< ( all - dp[ ( 3 - aktreszta )%3 ][count_blue] - poprawka + mod + mod + mod)<<endl;
	return ( all - dp[ ( 3 - aktreszta )%3 ][count_blue] - poprawka + mod + mod + mod)%mod;
}

void solve(){
	
	for(int i=0; i<s.size(); i++){
		char x = s[i];
		if(x == 'N')count_blue++;
		if(x == 'C')count_red++;
		if(x == 'Z')count_green++;
		if(i%2 == 0){
			if(x == 'Z')count_green_even++;
			if(x == 'C')count_red_even++;
		}
	}

	cout<<anwser()<<endl;
	while(q--){
		char c; int ind;
		cin>>ind>>c; ind--;
		char oldc = s[ind];
		if(oldc == 'N')count_blue--;
		if(oldc == 'C')count_red--;
		if(oldc == 'Z')count_green--;
		if(ind%2 == 0){
			if(oldc == 'Z')count_green_even--;
			if(oldc == 'C')count_red_even--;
			if(c == 'Z')count_green_even++;
			if(c == 'C')count_red_even++;
		}
		if(c == 'N')count_blue++;
		if(c == 'C')count_red++;
		if(c == 'Z')count_green++;
		s[ind] = c;
		cout<<anwser()<<endl;
	}	
}

int32_t main(){
	wczytaj();
	solve();
}