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
#include <cstdio>
#include <algorithm>

using namespace std;

constexpr static long long MOD = 1000000007;

long long A[200005][3];
char C[200005];
bool V[200005][2];

int main() {
    int n, q;
    int c=0, z=0;
    scanf("%d %d\n", &n, &q);
    A[0][0] = 1; A[0][1] = 0; A[0][2] = 0;
    for (int i=1; i<=n; i++) {
        A[i][0] = (A[i-1][0] + A[i-1][2]) % MOD;
        A[i][1] = (A[i-1][1] + A[i-1][0]) % MOD;
        A[i][2] = (A[i-1][2] + A[i-1][1]) % MOD;
    }

    int sv1=0, sv2=0, w;
    scanf("%s", C);
    for (int i=0; i<n; i++) {
        if (C[i] == 'Z') z ++;
        else if (C[i] == 'C') c ++;
        if (i & 1) {
            sv1 += C[i] != 'Z';
            sv2 += C[i] != 'C';
        } else {
            sv1 += C[i] != 'C';
            sv2 += C[i] != 'Z';
        }
    }
    if (n == 1) {
        printf("%d\n", C[0] == 'N' ? 2 : 1);
    } else {
        int mm = abs(c-z) % 3;
        w = 0;
        if (mm != 0) w += A[n-c-z][0];
        if (mm != 1) w += A[n-c-z][2];
        if (mm != 2) w += A[n-c-z][1];
        w %= MOD;
        if ((sv1 == n || sv2 == n) && (n&1)) w = (w + MOD - 1) % MOD;
        printf("%d\n", w);
    }

    while (q--) {
        int p;
        char cc;
        scanf("%d %c\n", &p, &cc);
        p --;

        if (C[p] == 'Z') z --;
        else if (C[p] == 'C') c --;
        if (p & 1) {
            sv1 -= C[p] != 'Z';
            sv2 -= C[p] != 'C';
        } else {
            sv1 -= C[p] != 'C';
            sv2 -= C[p] != 'Z';
        }
        C[p] = cc;
        if (C[p] == 'Z') z ++;
        else if (C[p] == 'C') c ++;
        if (p & 1) {
            sv1 += C[p] != 'Z';
            sv2 += C[p] != 'C';
        } else {
            sv1 += C[p] != 'C';
            sv2 += C[p] != 'Z';
        }

        if (n == 1) {
            printf("%d\n", C[0] == 'N' ? 2 : 1);
        } else {
            int mm = abs(c-z) % 3;
            w = 0;
            if (mm != 0) w += A[n-c-z][0];
            if (mm != 1) w += A[n-c-z][2];
            if (mm != 2) w += A[n-c-z][1];
            w %= MOD;
            if ((sv1 == n || sv2 == n) && (n&1)) w = (w + MOD - 1) % MOD;
            printf("%d\n", w);
        }
    }

    return 0;
}