Untitled

#include <bits/stdc++.h>
using namespace std;

#define ll          long long

void Init() {
    ios_base::sync_with_stdio(false),
            cin.tie(nullptr),
            cout.tie(nullptr);
#ifdef CLION
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#else
    //  freopen("input.txt", "r", stdin);
#endif
}

constexpr int MOD = 1e9 + 7, N = 2;

int mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

int add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

typedef vector<vector<int> > matrix;

matrix operator*(const matrix &lhs, const matrix &rhs) {
    int n = lhs.size();
    int m = rhs[0].size();
    int s1 = lhs[0].size(), s2 = rhs.size();
    assert(s1 == s2);
    matrix ret(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < s1; ++j)
            for (int k = 0; k < m; ++k)
                ret[i][k] = add(ret[i][k], mul(lhs[i][j], rhs[j][k]));
    return ret;
}

matrix Identity(int n) {
    matrix ret(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        ret[i][i] = 1;
    }
    return ret;
}

matrix mat_power(matrix x, ll p) {
    matrix res = Identity(x.size());
    while (p) {
        if (p & 1) res = (res * x);
        x = (x * x);
        p >>= 1;
    }
    return res;
}
matrix calc(char c) {
    matrix mat(2, vector<int>(2));
    for (char i = 'A'; i <= 'Z'; ++i) {
        if (c == i || c == '?') {
            if (i == 'H') {
                mat[0][1] += 1;
                mat[1][1] += 1;
            } else if (i == 'S' || i == 'D') {
                mat[1][0] += 1;
                mat[0][0] += 1;
            } else if (i == 'A' || i == 'E' || i == 'I' || i == 'O' || i == 'U') {
                mat[0][1] += 1;
                mat[1][0] += 1;
            } else {
                mat[0][0] += 1;
                mat[1][1] += 1;
            }
        }
    }
    return mat;
}

struct Tree {
    struct Node {
        matrix mat;

        Node() {
           mat = Identity(2);
        }
        Node(char c) {
            mat = calc(c);
        }
    };

    typedef Node T;

    T f(T a, T b) {
        Node ret;
        ret.mat = a.mat * b.mat;
        return ret;
    }

    vector<T> s;
    int n;

    Tree(int n = 0) : s(2 * n, Node()), n(n) {}

    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }

    T query(int b, int e) {
        e++;
        T ra = Node(), rb = Node();
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

void Mesh_JOO() {
    // n & q <= 2e5
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    Tree st(n);
    for (int i = 0; i < n; ++i) {
        st.update(i, Tree::Node(s[i]));
    }
    cout << st.query(0, n - 1).mat[1][1] << '\n';
    while (q--) {
        int idx;
        char c;
        cin >> idx >> c;
        idx--;
        st.update(idx, Tree::Node(c));
        cout << st.query(0, n - 1).mat[1][1] << '\n';
    }
}

int main() {
    Init();
    int t{1};
    // cin >> t;
    while (t--) {
        Mesh_JOO();
    }
    return 0;
}