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

using namespace std;

using ll = long long;

constexpr int mod = 1e9 + 7, max_base = 1 << 18, n_particles = 7;

enum Particle { C, Z, CZ, ZC, CZC, ZCZ, nil };

struct Reaction {
    Particle a, b, c;
};

struct Node {
    ll cnt[n_particles];
};

vector<Reaction> reactions = {
    {C, C, Z}, {C, Z, CZ}, {C, CZ, C}, {C, ZC, CZC}, {C, CZC, Z}, {C, ZCZ, CZ}, {C, nil, C},
    {Z, C, ZC}, {Z, Z, C}, {Z, CZ, ZCZ}, {Z, ZC, Z}, {Z, CZC, ZC}, {Z, ZCZ, C}, {Z, nil, Z},
    {CZ, C, CZC}, {CZ, Z, Z}, {CZ, CZ, CZ}, {CZ, ZC, CZ}, {CZ, ZC, ZC}, {CZ, CZC, CZC}, {CZ, ZCZ, Z}, {CZ, nil, CZ},
    {ZC, C, C}, {ZC, Z, ZCZ}, {ZC, CZ, ZC}, {ZC, CZ, CZ}, {ZC, ZC, ZC}, {ZC, CZC, C}, {ZC, ZCZ, ZCZ}, {ZC, nil, ZC},
    {CZC, C, Z}, {CZC, Z, CZ}, {CZC, CZ, C}, {CZC, ZC, CZC}, {CZC, CZC, Z}, {CZC, ZCZ, CZ}, {CZC, nil, CZC},
    {ZCZ, C, ZC}, {ZCZ, Z, C}, {ZCZ, CZ, ZCZ}, {ZCZ, ZC, Z}, {ZCZ, CZC, ZC}, {ZCZ, ZCZ, C}, {ZCZ, nil, ZCZ},
    {nil, C, C}, {nil, Z, Z}, {nil, CZ, CZ}, {nil, ZC, ZC}, {nil, CZC, CZC}, {nil, ZCZ, ZCZ}, {nil, nil, nil},
};

int base;
Node tree[2 * max_base];

void tree_update_node(int node) {
    for (auto [a, b, c] : reactions) {
        tree[node].cnt[c] = (tree[node].cnt[c] + tree[2 * node].cnt[a] * tree[2 * node + 1].cnt[b]) % mod;
    }
}

void tree_clear_node(int node) {
    node += base - 1;
    fill(tree[node].cnt, tree[node].cnt + n_particles, 0);
}

void tree_set_leaf(int node, char c) {
    tree_clear_node(node);
    node += base - 1;
    if (c == 'C') {
        tree[node].cnt[C] = 1;
    } else if (c == 'Z') {
        tree[node].cnt[Z] = 1;
    } else {
        tree[node].cnt[C] = 1;
        tree[node].cnt[Z] = 1;
    }
}

void tree_set(int node, char c) {
    tree_set_leaf(node, c);
    node += base - 1;
    while (node /= 2) {
        tree_clear_node(node - base + 1);
        tree_update_node(node);
    }
}

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

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

    base = 1 << (__lg(n - 1) + 1);

    for (int i = 0; i < base; ++i) {
        tree_clear_node(i + 1);
    }
    for (int i = n; i < base; ++i) {
        tree[base + i].cnt[nil] = 1;
    }

    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;

        tree_set_leaf(i + 1, c);
    }

    for (int i = base - 1; i > 0; --i) {
        tree_update_node(i);
    }


    cout << (tree[1].cnt[C] + tree[1].cnt[Z]) % mod << "\n";
    while (q--) {
        int node;
        char c;
        cin >> node >> c;
        tree_set(node, c);
        cout << (tree[1].cnt[C] + tree[1].cnt[Z]) % mod << "\n";
    }
}