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

// typedef pair<int,int> pii;
// typedef long long ll;


#define M 1'000'000'007
#define inv3 333'333'336


int main(){
    int n, q, g[2];
    int count[255];
    int P[200'000];

    auto add = [&](char c, int i){
        count[c]++;
        if(c=='N')  return  g[0]++,         g[1]++;
        if(c=='Z')  return  g[0]+=i&1,      g[1]+=i&1^1;
                    return  g[0]+=i&1^1,    g[1]+=i&1;
    };
    auto sub = [&](char c, int i){
        count[c]--;
        if(c=='N')  return  g[0]--,         g[1]--;
        if(c=='Z')  return  g[0]-=i&1,      g[1]-=i&1^1;
                    return  g[0]-=i&1^1,    g[1]-=i&1;
    };

    auto calc = [&](){
        int l = count['N'], res;
        if(count['Z']%3==count['C']%3) res = 2LL*(P[l]-(l&1?-1:1))*inv3%M;
        else res = (2LL*P[l]+(l&1?-1:1))*inv3%M;
        if(n&1 && n>1) res = (res*1LL - (g[0]==n) - (g[1]==n) + M)%M;
        return res;
    };
    
    for(int i=P[0]=1;i<200'000;i++) P[i]=2LL*P[i-1]%M;
    for(int i=0;i<255;i++) count[i]=0;
    g[0]=g[1]=0;
    
    cin>>n>>q;
    string s(n,' ');
    for(int i=0;i<n;i++) cin>>s[i], add(s[i], i);

    cout<<calc()<<endl;
    int i; char c;
    while(q--){
        cin>>i>>c; i--;
        sub(s[i],i), s[i]=c, add(c,i);
        // cout<<"["<<count['N']<<" "<<count['C']<<" "<<count['Z']<<" "<<g[0]<<" "<<g[1]<<" "<<"]";
        cout<<calc()<<endl;
    }


}