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

using namespace std;

typedef long long lld;

const lld MOD = 1e9+7;
const lld INV3 = 333'333'336;

int n, q;
int C, D, par[2][2];

vector<int> powtwo;
string s;

void calc_powtwo() {
    powtwo.resize(n + 1, 0);
    powtwo[0] = 1;
    for (int i = 1; i <= n; ++i) {
        powtwo[i] = 2 * powtwo[i - 1];
        if (powtwo[i] >= MOD)
            powtwo[i] -= MOD;
    }
}

bool parities() {
    return (par[0][0] == 0 && par[1][1] == 0) || (par[0][1] == 0 && par[1][0] == 0);
}

// 2^C - sum_{C != D-C mod 3} (C choose k)
int calc() {
    lld N = powtwo[C];
    int mod = (D - C) % 3;
    lld res = (N - (1 << (C % 2))) * INV3 % MOD * 2;

    if ((mod + C) % 3 != 0)
        ++res;
    else if (C % 2 == 1)
        res += 2;
    if (n % 2 == 1 && parities())
        res -= (C == n ? 2 : 1);

    return res % MOD;
}

void parse_diff(int idx, int val) {
    if (s[idx] == 'N') C += val;
    else if (s[idx] == 'Z') {
        D -= val;
        par[1][idx % 2] += val;
    }
    else {
        D += val;
        par[0][idx % 2] += val;
    }
}

void handleone() {
    char s; cin >> s;
    cout << (s == 'N' ? 2 : 1) << '\n';
    for (int i = 0; i < q; ++i) {
        int pos;
        cin >> pos >> s;
        cout << (s == 'N' ? 2 : 1) << '\n';
    }
}

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

    cin >> n >> q;

    if (n == 1) {
        handleone();
        return 0;
    }

    calc_powtwo();
    
    cin >> s;
    for (const char &c : s) {
        if (c == 'N') ++C;
        else if (c == 'C') ++D;
        else --D;
    }
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'N') continue;
        ++par[s[i] == 'Z'][i % 2];
    }

    cout << calc() << '\n';
    for (int i = 0; i < q; ++i) {
        int pos; char val;
        cin >> pos >> val;

        parse_diff(pos - 1, -1);
        s[pos - 1] = val;
        parse_diff(pos - 1, 1);
        
        cout << calc() << '\n';
    }
}