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
// clang-format off
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<"}";}
#ifdef DEBUG
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<"\n";}(X)
#else
#define debug(...) {}
#endif
// clang-format on

// clang-format off
const int MOD = 998244353;
int add(const int &a, const int &b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(const int &a, const int &b) { return a >= b ? a - b : MOD + a - b; }
// clang-format on

int N, Q;
string str;
const int nchars = 6;

// int
// calc_distinct(const string& str)
// {
//     array<int, nchars> per_char = {0};
//     int res                     = 1;
//     REP (i, ssize(str)) {
//         auto &repetitions = per_char[str[i] - 'a'];
//         int bef          = res;
//         res              = sub(add(res, res), repetitions);
//         repetitions = bef;
//         debug(i, res);
//     }
//     return res;
// }

int
calc_distinct(const string& str)
{
    vector<int> dp(ssize(str) + 1), last(nchars);
    dp[0] = 1;
    FOR (i, 1, ssize(str)) {
        auto& l = last[str[i - 1] - 'a'];
        dp[i]   = add(dp[i - 1], dp[i - 1]);
        if (l) dp[i] = sub(dp[i], dp[l - 1]);
        l = i;
    }
    return dp.back();
}

int
calc_appearing_once(const string& str)
{
    vector<int> dp(ssize(str) + 1), last(nchars);
    FOR (i, 1, ssize(str)) {
        auto& l = last[str[i - 1] - 'a'];
        dp[i]   = 0;

        if (l) {
            // Patters created by l repeats
            // we can rescue than by appending current char
            FOR (pos, l, i - 1) dp[i] = add(dp[i], dp[pos]);
            dp[l] = 0;
        }

        else
        {
            // We can append current char to every previously created guy
            FOR (pos, 1, i - 1) dp[i] = add(dp[i], dp[pos]);

            // Also, we create a new subsequence being ourself
            dp[i] = add(dp[i], 1);
        }

        l = i;
    }
    int res = 1;
    REP (i, ssize(dp)) res = add(res, dp[i]);
    return res;
}

int
main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> Q >> str;
    cout << sub(calc_distinct(str), calc_appearing_once(str)) << "\n";
    while (Q--) {
        int pos;
        char ch;
        cin >> pos >> ch;
        str[pos - 1] = ch;

        int distinct = calc_distinct(str);
        int once     = calc_appearing_once(str);
        debug(distinct, once);
        cout << sub(distinct, once) << "\n";
    }
    return 0;
}