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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define debug(...) __VA_ARGS__
#else
#define debug(...) {}
#endif
const ll mod = 1e9+7;
ll fastpow(ll a, ll b){
    ll w = 1;
    while (b){
        if (b%2) w = (w*a)%mod;
        a = (a*a)%mod;
        b /= 2;
    }       
    return w%mod;
}
ll dod[2];
ll tab[6][3];
ll ilesposobow(ll n, ll k, ll reszta, ll dl){
    reszta = ((reszta-k)%3+3)%3;
    //cout<<reszta<<"\n";
    //cout<<fastpow(2,n)<<"\n";
    ll val;
    if (n%2) val = ((fastpow(2,n)+1)*fastpow(3,mod-2))%mod;
    else val = ((fastpow(2,n)+2)*fastpow(3,mod-2))%mod;
    val += tab[n%6][reszta];
    //cout<<val<<"\n";
    //cout<<n<<"\n";
    ll wy = (fastpow(2,n)-val+mod)%mod;
    if (dl%2){
        if (dod[0] == dl) wy--;
        if (dod[1] == dl) wy--;
    }
    return (wy+mod)%mod;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i;
    //Dziwna tablica
    tab[0][1] = tab[0][2] = -1;
    tab[1][2] = -1;
    tab[2][0] = tab[2][2] = -1;
    tab[3][0] = -1;
    tab[4][0] = tab[4][1] = -1;
    tab[5][1] = -1;
    //
    ll n,m;
    cin>>n>>m;   
    string s;
    cin>>s;
    if (n == 1){
        if (s[0] == 'N') cout<<2<<"\n";
        else cout<<1<<"\n";
        while (m--){
            ll pos;
            char akt;
            cin>>pos>>akt;
            s[0] = akt;
            if (s[0] == 'N') cout<<2<<"\n";
            else cout<<1<<"\n";
        }
        return 0;
    }
    ll ilen = 0;
    ll ilez = 0;
    for (char c : s){
        if (c == 'N') ilen++;
        if (c == 'Z') ilez++;
    }
    for (i = 0; i < (ll)s.size(); i++){
        if (s[i] != 'C'){
            
            dod[i%2]++;
        }
        if (s[i] != 'Z'){
            dod[(i+1)%2]++;
        }
    } 
    cout<<ilesposobow(ilen,ilez,(3-n%3)%3,n)<<"\n";
    while (m--){
        ll pos;
        char c;
        cin>>pos>>c;
        if (s[pos-1] == 'N') ilen--;
        if (s[pos-1] == 'Z') ilez--;
        if (s[pos-1] != 'C') dod[(pos-1)%2]--;
        if (s[pos-1] != 'Z') dod[pos%2]--;
        if (c == 'N') ilen++;
        if (c == 'Z') ilez++;
        if (c != 'C') dod[(pos-1)%2]++;
        if (c != 'Z') dod[pos%2]++;
        s[pos-1] = c;
        cout<<ilesposobow(ilen,ilez,(3-n%3)%3,n)<<"\n";
    }   
    return 0;
}