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
#include<cstdio>
#include<vector>
#include<map>
#include<utility>
#include<iostream>
long long int mod = 1000000007;


int qpow(int base,int exp,long long int mod)
{
	long long int x=base;
	long long int  ans=1;
	while(exp)
	{
	    if(exp % 2!=0)
	        ans*=x;
	    ans = ans % mod;
	    x = x * x % mod;
	    exp/=2;
	}
	return (mod + ans) % mod;
}

void div3(long long int &n){
    if(n%3 == 0)
        n = n / 3;
    else if(n%3 == 1)
	n = n / 3 + 333333336;
    else
	n = n / 3 + 2 * 333333336;
}

long long int magic_fun(int mod3, int k){
    mod3 = (mod3 - k + 3) % 3;
    mod3 = (mod3  + 3) % 3;

    long long int res = qpow(2, k, mod);
    if (k % 2 == 0)
        res-=1;
    else
        res-=2;
    div3(res);
     
    if(k%6 == 2 * mod3 or k%6 == (2*mod3-1 + 6) % 6 or k%6 == (2*mod3+7) % 6)
        res++;
    return (qpow(2, k, mod) - res + mod) % mod;
}



int main(){

int n, q;
char c;
std::vector<std::map<char, int>> odd_even;
std::vector<std::pair<int, char>> modifications;

odd_even.push_back({{'N', 0}, {'C', 0}, {'Z', 0}});
odd_even.push_back({{'N', 0}, {'C', 0}, {'Z', 0}});

std::vector<char> v;
v.push_back('0');
scanf("%d %d", &n, &q);

for(int i=1; i <= n; i++){
    scanf(" %c", &c);
    v.push_back(c);
    odd_even[i%2][c]++;
}

int num = 0;
char new_color = '0';

modifications.push_back({0, '0'});

for(int j=0; j <q; j++){
    scanf("%d %c", &num, &new_color);
    modifications.push_back({num, new_color});
}
for(int j=0; j <q+1; j++){
    num = modifications[j].first;
    new_color = modifications[j].second;
    if (v[num] != new_color){
        odd_even[num%2][new_color]++;
        odd_even[num%2][v[num]]--;
        v[num] = new_color;
    }
    int cmz = (odd_even[0]['C'] + odd_even[1]['C'] - odd_even[0]['Z'] - odd_even[1]['Z']) % 3;
    cmz = (cmz + 3) % 3;
    long long int result = magic_fun(cmz, odd_even[0]['N'] + odd_even[1]['N']);
    if ((odd_even[0]['C'] == 0 and odd_even[1]['Z'] == 0) and n%2 == 1)
        result--; 
    if ((odd_even[1]['C'] == 0 and odd_even[0]['Z'] == 0) and n%2 == 1)
        result--;
    printf("%lld\n", result);
    scanf("%d %c", &num, &new_color);
     
}

return 0;
}