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

using namespace std;

long long n,q;
long long mod = 1e9 + 7;
vector<long long> kom[3][3];
vector<long long> d;
string t;
bool _log = 0;

void Set_up_kom(){
    d.assign(n+1,0);
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            kom[i][j].assign(n+1,0);
        }
    }
    long long j = 1;
    long long o = 1;
    for(int i = 0; i<n; i++){
        kom[0][0][i] = ((2*j + o)*333333336)%mod;//1
        kom[0][1][i] = (2*(-j + o)*333333336)%mod;//2
        kom[0][2][i] = (2*(j + 2*o)*333333336)%mod;//3
        kom[1][0][i] = ((-j + o)*333333336)%mod;//5
        kom[1][1][i] = ((j + 2*o)*333333336)%mod;//5
        kom[1][2][i] = ((-j + 4*o)*333333336)%mod;//4
        kom[2][0][i] = ((-j + o)*333333336)%mod;//5
        kom[2][1][i] = ((j + 2*o)*333333336)%mod;//5
        kom[2][2][i] = ((-j + 4*o)*333333336)%mod;//4
        j*=-1;
        o = (o*8)%mod;
    }
    
    long long allk = 1;
    for(int i = 0; i<=n; i++){
        d[i] = allk;
        allk = (allk*2)%mod;
    }
}

struct Count{
    int z = 0;
    int c = 0;
    int n = 0;
};
Count num[2];

int policz(){
    long long res = 0;
    if(num[0].z == 0 && num[1].c == 0 && n%2)res++;
    if(num[0].c == 0 && num[1].z == 0 && n%2)res++;
    long long Z = num[0].z + num[1].z;
    long long C = num[0].c + num[1].c;
    long long N = num[0].n + num[1].n;
    long long D = abs(C-Z)%3;
    res += kom[D][N%3][N/3];    
    //cout<<D<<" "<<N<<" "<<kom[D][N%3][N/3]<<" \n";
    return ( d[num[0].n + num[1].n] - res + mod) % mod;
}


int main(){
    _log = 0;
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>q>>t;
    Set_up_kom();
    if(_log){for(int i = 0; i<n; i++)cout<<kom[i]<<"\n";cout<<"\n";}
    for(int i = 0; i<n; i++){
        if(t[i] == 'Z')num[i%2].z++;
        if(t[i] == 'N')num[i%2].n++;
        if(t[i] == 'C')num[i%2].c++;
    }
    cout<<policz()<<"\n";
    
    for(int i = 0; i<q; i++){
        int ind;
        char c;
        cin>>ind>>c;
        ind --;
        if(t[ind] == 'Z')num[ind%2].z--;
        if(t[ind] == 'N')num[ind%2].n--;
        if(t[ind] == 'C')num[ind%2].c--;
        t[ind] = c;
        if(c == 'Z')num[ind%2].z++;
        if(c == 'N')num[ind%2].n++;
        if(c == 'C')num[ind%2].c++;
        cout<<policz()<<"\n";
    }
    return 0;
}