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

using namespace std;

typedef long long ll;
const int MOD = 1e9+7;

ll cnt[255];
ll cntNP[255][2]; // Zliczaj litery na przystych / nieparzystych pozycjach

ll pot(ll a, ll n){
    if(n==0) return 1;
    if(n==1) return a%MOD;
    if(n==2) return (a*a)%MOD;
    if(n&1) return (pot(pot(a,n/2),2)*a)%MOD;
    return pot(pot(a,n/2),2);
}

ll inv(ll a){
    return pot(a,MOD-2);
}

ll fTab[6] = {2,1,-1,-2,-1,1};

ll f(ll n){
    return fTab[n%6];
}

ll calc(){
    int n = cnt['C']+cnt['Z']+cnt['N'];
    ll res0 = pot(2,cnt['N']);
    ll res1 = res0;
    ll res2 = res0;

    res0 = (res0 + f(cnt['N']) + MOD)%MOD;
    res1 = (res1 + f(cnt['N']+2) + MOD)%MOD;
    res2 = (res2 + f(cnt['N']+4) + MOD)%MOD;
    res0 = (res0 * inv(3)) % MOD;
    res1 = (res1 * inv(3)) % MOD;
    res2 = (res2 * inv(3)) % MOD;

    bool czyMoznaNaPrzemianC = (cntNP['Z'][0]==0) && (cntNP['C'][1]==0);
    bool czyMoznaNaPrzemianZ = (cntNP['C'][0]==0) && (cntNP['Z'][1]==0);

    ll toSub = czyMoznaNaPrzemianC+czyMoznaNaPrzemianZ;

    res0 = (pot(2,cnt['N']) - res0 + MOD)%MOD;
    res1 = (pot(2,cnt['N']) - res1 + MOD)%MOD;
    res2 = (pot(2,cnt['N']) - res2 + MOD)%MOD;
    if(n%2==1){
        res0 -= toSub;
        res1 -= toSub;
        res2 -= toSub;
    }
    if(abs(cnt['N']+cnt['C']-cnt['Z']+3333333)%3 == 0){
        return res0;
    }else if(abs(cnt['N']+cnt['C']-cnt['Z']+3333333)%3 == 1){
        return res1;
    }
    return res2;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    int n,q,a;
    char c;

    cin >> n >> q >> s;
    for(int i=0; i<n; ++i){
        ++cntNP[s[i]][i%2];
        ++cnt[s[i]];
    }
    if(n==1){
        cout << ((s[0]=='N')?2:1) << '\n';
    }else{
        cout << calc() << '\n';
    }
    while(q--){
        cin >> a >> c;
        --a;
        --cnt[s[a]];
        --cntNP[s[a]][a%2];
        ++cnt[c];
        ++cntNP[c][a%2];
        s[a] = c;
        if(n==1){
            cout << ((s[0]=='N')?2:1) << '\n';
        }else{
            cout << calc() << '\n';
        }
    }
    return 0;
}