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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <list>
using namespace std;
const int MOD = 1000000007;

struct Node {
    bool null;
    int C, Z, B;
    int CC, CZ, CB;
    int ZC, ZZ, ZB;
    int BC, BZ, BB;

    void from_char(char x) {
        null = false;
        C = (x == 'C' || x == 'N');
        Z = (x == 'Z' || x == 'N');
        B = CC = CZ = CB = ZC = ZZ = ZB = BC = BZ = BB = 0;
    }

    friend Node operator*(const Node& left, const Node& right) {
        if (left.null)
            return right;
        if (right.null)
            return left;
        Node result;
        result.null = false;

#define M(x, y) ((long long)(left.x) * (long long)(right.y))
#define Mwo(x, wo, y) (((long long)(left.x) - (long long)(left.wo)) * (long long)(right.y))
#define R(t, x) result.t = (x) % MOD

        R(C, M(Z, Z) + M(C, B) + M(B, C));
        R(Z, M(C, C) + M(B, Z) + M(Z, B));
        R(B, M(B, B) + M(Z, C) + M(C, Z));

        R(CC, M(CC, B) + M(CZ, Z) + M(CB, C)   +   Mwo(C, CB, C)   +   Mwo(Z, CC, ZC) + Mwo(B, CZ, CC));
        R(CZ, M(CC, C) + M(CZ, B) + M(CB, Z)   +   Mwo(C, CB, Z)   +   Mwo(Z, CC, ZZ) + Mwo(B, CZ, CZ));
        R(CB, M(CC, Z) + M(CZ, C) + M(CB, B)   +   Mwo(C, CB, B)   +   Mwo(Z, CC, ZB) + Mwo(B, CZ, CB));

        R(ZC, M(ZC, B) + M(ZZ, Z) + M(ZB, C)   +   Mwo(Z, ZB, C)   +   Mwo(C, ZZ, CC) + Mwo(B, ZC, ZC));
        R(ZZ, M(ZC, C) + M(ZZ, B) + M(ZB, Z)   +   Mwo(Z, ZB, Z)   +   Mwo(C, ZZ, CZ) + Mwo(B, ZC, ZZ));
        R(ZB, M(ZC, Z) + M(ZZ, C) + M(ZB, B)   +   Mwo(Z, ZB, B)   +   Mwo(C, ZZ, CB) + Mwo(B, ZC, ZB));

        R(BC, M(BC, B) + M(BZ, Z) + M(BB, C)   +   Mwo(B, BB, C)   +   Mwo(C, BC, ZC) + Mwo(Z, BZ, CC));
        R(BZ, M(BC, C) + M(BZ, B) + M(BB, Z)   +   Mwo(B, BB, Z)   +   Mwo(C, BC, ZZ) + Mwo(Z, BZ, CZ));
        R(BB, M(BC, Z) + M(BZ, C) + M(BB, B)   +   Mwo(B, BB, B)   +   Mwo(C, BC, ZB) + Mwo(Z, BZ, CB));

#undef R
#undef Mwo
#undef M

        return result;
    }

    int value() const {
        return (CC + ZZ) % MOD;
    }
};

class Pine {
    int start, size;
    vector<Node>T;

    public:
    Pine(const string& init) {
        start = 1;
        while (start < (int)init.size())
            start *= 2;
        size = 2*start;
        T.resize(size);

        for (int i = 0; i < (int)init.size(); i++)
            T[i + start].from_char(init[i]);
        for (int i = init.size(); i < start; i++)
            T[i + start].null = true;
        for (int i = start - 1; i >= 1; i--)
            T[i] = T[2*i] * T[2*i+1];
    }

    const Node& root() const {
        return T[1];
    }

    void set(int pos, Node val) {
        pos += start;
        T[pos] = val;
        while (pos > 1) {
            pos /= 2;
            T[pos] = T[2*pos] * T[2*pos+1];
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    string A;
    cin >> A;

    Pine pine(A);
    auto value = [&]() {
        if (n == 1)
            return (A[0] == 'N') ? 2 : 1;
        return pine.root().value();
    };
    cout << value() << "\n";


    while (q--) {
        int pos;
        string color;
        cin >> pos >> color;
        Node new_node;
        new_node.from_char(color[0]);
        pine.set(pos - 1, new_node);
        A[pos - 1] = color[0];
        cout << value() << "\n";
    }

    return 0;
}