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

using namespace std;


long long distinct(string s, vector<long long> &dp, vector<long long> &sum, vector<vector<int>> &last1, int from) {
    int n = s.size();
    dp[0] = 1;
    sum[0] = 1;

    for (int i = from; i < n; i++) {
        dp[i+1] = (sum[i] - ((i == 0 || last1[s[i] - 'a'][i - 1] == -1) ? 0 : sum[last1[s[i] - 'a'][i-1]]))% 998244353;
        sum[i+1] = (sum[i] + dp[i+1]) % 998244353;
    }

    return (sum[n]-1) % 998244353;
}

long long unique(string s, vector<long long> &dp, vector<vector<int>> &last1, int from) {
    int n = s.size();

    for (int i = from; i < n; i++) {
        long long next = 0;
        for (int j = 0; j < 6; j++) {
            if (i > 0 && last1[j][i-1] > last1[s[i] - 'a'][i-1]) {
                next += dp[last1[j][i-1]];
            }
        }
        next += (i == 0 || last1[s[i] - 'a'][i-1] == -1 ? 1 : dp[last1[s[i] - 'a'][i-1]]);
        dp[i] = next % 998244353;
    }
    long long sum = 0;
    for (int i = 0; i < 6; i++) {
        if (last1[i][last1[i].size() - 1] != -1) {
            sum += dp[last1[i][last1[i].size() - 1]];
            sum %= 998244353;
        }
    }
    return sum;
}

void set_last(vector<vector<int>> &last, string s, int from) {
    for (int i = from; i < s.size(); i++) {
        for (int j = 0; j < 6; j++) {
            if (s[i] - 'a' == j) {
                last[j][i] = i;
            } else if (i > 0) {
                last[j][i] = last[j][i-1];
            } else {
                last[j][i] = -1;
            }
        }
    }
}


int main() {
    bool swapped = false;
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    string s;
    cin >> s;

    vector<pair<long long, char>> queries;
    vector<long long> unique_dp(n + 1, 0);
    vector<long long> distinct_dp(n + 1, 0);

    for (int i = 0; i < q; i++) {
        long long p;
        char c;
        cin >> p >> c;
        queries.push_back({p, c});
    }

    long long queries_sum = 0;
    for (int i = 0; i < q; i++) {
        queries_sum += queries[i].first;
    }

    if (q > 0 && queries_sum / q < n / 2) {
        swapped = true;
        reverse(s.begin(), s.end());
    }
    vector<vector<int>> last(6, vector<int>(n, -1));
    set_last(last, s, 0);
    vector<long long> sum(n + 1, 0);
    cout << ((distinct(s, distinct_dp, sum, last, 0) - unique(s, unique_dp, last, 0))% 998244353+  998244353) %  998244353 << '\n';

    for (int i = 0; i < q; i++) {
        long long p;
        if (swapped) {
            p = n - queries[i].first + 1;
        } else {
            p = queries[i].first;
        }
        s[p - 1] = queries[i].second;
        set_last(last, s, p - 1);
        cout << ((distinct(s, distinct_dp, sum, last, p-1) - unique(s, unique_dp, last, p-1))% 998244353+  998244353) %  998244353 << '\n';
    }

    return 0;
}