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

using namespace std;


const int MOD = 1'000'000'007;


struct update {
    int pos; char c;
};

void add(int &x, int v) {
    x += v;
    if (x >= MOD) {
        x -= MOD;
    }
}

vector <int> solve(int n, int q, string &s, vector <update> &updates) {
    vector <vector<int>> numWays(n + 1, vector <int> (3, 0));
    numWays[0][0] = 1;

    for (int i = 0; i < n; i++) for (int rem = 0; rem < 3; rem++) for (int nxt : {1, 2}) {
        int remNew = (rem + nxt) % 3;
        add(numWays[i + 1][remNew], numWays[i][rem]);
    }

    vector <int> numDiff(2, 0);
    int numWildcard = 0, totalRem = 0;

    auto update = [&](int i, int chg) {
        if (s[i] == 'N') {
            numWildcard += chg;
        } else {
            int rem = s[i] == 'Z' ? 2 : 1;
            if (chg == -1) {
                rem = 3 - rem;
            }

            totalRem = (totalRem + rem) % 3;

            int bitHere = s[i] == 'Z';
            for (int d = 0; d < 2; d++) {
                int bitExp = d ^ (i % 2);
                if (bitHere != bitExp) {
                    numDiff[d] += chg;
                }
            }
        }
    };

    auto getAns = [&]() {
        if (n == 1) {
            return numWildcard + 1;
        }

        int ans = 0;
        for (int rem = 0; rem < 3; rem++) if ((rem + totalRem) % 3 != 0) {
            add(ans, numWays[numWildcard][rem]);
        }

        if (n % 2) {
            for (int d = 0; d < 2; d++) if (!numDiff[d]) {
                add(ans, MOD - 1);
            }
        }

        return ans;
    };

    for (int i = 0; i < n; i++) {
        update(i, 1);
    }

    vector <int> ans(q + 1);
    ans[0] = getAns();

    for (int i = 0; i < q; i++) {
        update(updates[i].pos, -1);
        s[updates[i].pos] = updates[i].c;
        update(updates[i].pos, 1);

        ans[i + 1] = getAns();
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    string init;
    cin >> init;

    vector <update> updates(q);
    for (int i = 0; i < q; i++) {
        cin >> updates[i].pos >> updates[i].c;
        updates[i].pos--;
    }

    auto ans = solve(n, q, init, updates);
    for (int x : ans) {
        cout << x << '\n';
    }

    return 0;
}