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 <iostream>

using namespace std;

int main() {
    int N,Q;
    string S;
    const long long C = 200001, P = 1000000007;
    long long a[C],b[C],c[C];
    a[0] = a[1] = a[2] = 1;
    b[0] = 0; b[1] = 1; b[2] = 2;
    c[0] = 0; c[1] = 0; c[2] = 1;
    for(int i=3; i<C; ++i) {
        a[i] = (3*a[i-1] - 3*a[i-2] + 2*a[i-3] + 3*P) % P;
        b[i] = (3*b[i-1] - 3*b[i-2] + 2*b[i-3] + 3*P) % P;
        c[i] = (3*c[i-1] - 3*c[i-2] + 2*c[i-3] + 3*P) % P;
    }
    
    cin>>N>>Q;
    cin>>S;
    
    string s1,s2;
    int r1,r2;
    s1 = s2 = "";
    r1 = r2 = 0;
    for(int i=0; i<N; ++i) {
        if(i % 2 == 0) {
            s1 += 'C';
            s2 += 'Z';
        }
        else {
            s1 += 'Z';
            s2 += 'C';
        }
        if(S[i] == 'C' && s1[i] == 'Z') r1++;
        if(S[i] == 'Z' && s1[i] == 'C') r1++;
        if(S[i] == 'C' && s2[i] == 'Z') r2++;
        if(S[i] == 'Z' && s2[i] == 'C') r2++;
    }
    int lC,lZ,lN;
    lC = lZ = lN = 0;
    for(int i=0; i<N; ++i) {
        if(S[i] == 'C') lC++;
        else if(S[i] == 'Z') lZ++;
        else lN++;
    }
    long long reszta,ans;
    reszta = (-2*lC + 2*lZ + 2*lN + 3*N) % 3;
    if(reszta == 0) ans = (b[lN] + c[lN]) % P;
    if(reszta == 1) ans = (a[lN] + c[lN]) % P;
    if(reszta == 2) ans = (a[lN] + b[lN]) % P;
    if(N % 2 == 1 && N > 1) {
        if(r1 == 0) ans = (ans - 1 + P) % P;
        if(r2 == 0) ans = (ans - 1 + P) % P;
    }
    cout<<ans<<endl;
    
    for(int i=0; i<Q; ++i) {
        int K;
        char L;
        cin>>K>>L;
        K--;
        char l;
        l = S[K];
        S[K] = L;
        if(l == 'C') lC--; if(l == 'Z') lZ--; if(l == 'N') lN--;
        if(L == 'C') lC++; if(L == 'Z') lZ++; if(L == 'N') lN++;
        
        if(s1[K] == 'C' && l == 'Z') r1--;
        if(s1[K] == 'Z' && l == 'C') r1--;
        if(s1[K] == 'C' && L == 'Z') r1++;
        if(s1[K] == 'Z' && L == 'C') r1++;
        
        if(s2[K] == 'C' && l == 'Z') r2--;
        if(s2[K] == 'Z' && l == 'C') r2--;
        if(s2[K] == 'C' && L == 'Z') r2++;
        if(s2[K] == 'Z' && L == 'C') r2++;
        
        reszta = (-2*lC + 2*lZ + 2*lN + 3*N) % 3;
        if(reszta == 0) ans = (b[lN] + c[lN]) % P;
        if(reszta == 1) ans = (a[lN] + c[lN]) % P;
        if(reszta == 2) ans = (a[lN] + b[lN]) % P;
        if(N % 2 == 1 && N > 1) {
            if(r1 == 0) ans = (ans - 1 + P) % P;
            if(r2 == 0) ans = (ans - 1 + P) % P;
        }
        cout<<ans<<endl;
    }
    
    
    return 0;
}