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>
#define ll long long
using namespace std;

const int MOD = 998244353, N = 5e4, LETTERS = 6, MY_N = 1e4;

int n, q, x;
int occ_pref[LETTERS][N + 1], occ_suff[LETTERS][N + 1], res[MY_N + 2][MY_N + 2];
ll dp[N + 1];

char c;
string s;

int get_first(int i, int a, int b) {
    int first = occ_suff[i][a];
    if (first > b) return n + 1;
    return first;
}

int get_last(int i, int a, int b) {
    int last = occ_pref[i][b];
    if (last < a) return 0;
    return last;
}

void calc_dp(){
    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= n + 1; j++){
            res[i][j] = -1;
        }
    }
    dp[0] = 0;
    dp[1] = 1;
    for(int j = 2; j <= n; j++){
        int prev = get_last(s[j - 1] - 'a', 1, j - 1);
        if(prev < 1) dp[j] = 1;
        else dp[j] = 0;
        prev = max(prev, 1);
        dp[j] = (dp[j] + 2*dp[j-1] - dp[prev-1] + MOD) % MOD;
    }
}

int solve(int a, int b) {
    if(res[a][b] != -1) {
        return res[a][b];
    }
    if (a == b) {
        return res[a][b] = 1;
    }
    if (b < a) {
        return res[a][b] = 0;
    }
    int temp = 0;
    int lb = n + 1;
    int rb = 0;
    if(a > 1) lb = get_first(s[a - 2] - 'a', a, b);
    if(b < n) rb = get_last(s[b] - 'a', a, b);
    for(int i = 0 ; i < LETTERS; i++){
        for(int j = 0; j < LETTERS; j++){
            int l = get_first(i, a, b);
            int r = get_last(j, a, b);
            if (l > r || l > lb || r < rb) continue;
            if(get_last(s[l - 1] - 'a', l + 1, r - 1) < l && get_last(s[r - 1] - 'a', l + 1, r - 1) < l) temp++;
            temp = (temp + solve(l + 1, r - 1)) % MOD;
        }
    }
    return res[a][b] = temp;
}

void calc_occ() {
    for(int i = 0; i < LETTERS; i++) {
        for(int j = 1; j <= n; j++) {
            occ_pref[i][j] = s[j-1] - 'a' == i ? j : occ_pref[i][j-1];
        }

        occ_suff[i][n+1] = n+1;
        for(int j = n; j >= 1; j--) {
            occ_suff[i][j] = s[j-1] - 'a' == i ? j : occ_suff[i][j+1];
        }
    }
}

int wynik() {
    return (dp[n] - solve(1, n) + MOD) % MOD;
}

int main() {
    cin>>n>>q;
    cin>>s;
    calc_occ();
    calc_dp();
    cout<<wynik()<<"\n";

    for(int i = 1 ; i<=q; i++){
        cin>>x>>c;
        s[x - 1] = c;
        calc_occ();
        calc_dp();
        cout<<wynik()<<"\n";
    }
}