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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
#include <array>

using namespace std;

const int M = 998244353;

struct modular
{
    int a;
    modular operator + (modular b)
    {
        modular res;
        res.a = (a+b.a) % M;
        return res;
    }
    modular operator + (int b)
    {
        modular res;
        res.a = (a+b) % M;
        return res;
    }
    modular operator - (modular b)
    {
        modular res;
        res.a = (M+a-b.a) % M;
        return res;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin>>n>>q;
    string s;
    cin>>s;
    ++q;
    while (q--)
    {
        vector<array<modular, 6>> vec(n+1);
        for(int i=0; i<n; i++)
        {
            int j = s[i] - 97;
            vec[i+1][j] = vec[i][0] + vec[i][1] + vec[i][2] + vec[i][3] + vec[i][4]
                + vec[i][5] + 1;
            for(int k = 0; k < 6; k++) //O(6)
            {
                if(k==j) continue;
                vec[i+1][k] = vec[i][k];
            }
        }
        modular sum1{0};
//        for(auto& x : vec)
//        {
            for(auto y : vec[n])
                sum1 = sum1 + y;
//                cout<<y<<" ";
//            cout<<"\n";
//        }
/*        for(auto& x : vec)
        {
            for(auto y : x)
                cout<<y.a<<" ";
            cout<<"\n";
        }
*/
        vector<array<modular, 6>> vec2(n+1);
        array<array<bool, 6>, 6> vb{};
        for(int k=0; k<6; k++)
            vb[k][k] = 1;
        array<bool, 6> used{};
        for(int i=0; i<n; i++)
        {
            vec2[i+1] = vec2[i];
//            vb[i+1] = vb[i];
            int j = s[i] - 97;
            if((i == 0) || (s[i] != s[i-1]))
            {
                vec2[i+1][j] = modular{!used[j]};
                for(int k=0; k<6; k++)
                    vec2[i+1][j] = vec2[i+1][j] + 
                        (vb[k][j]?vec2[i][k]:modular{0});
                for(int k=0; k<6; k++)
                {
                    if(k!=j)
                    {
                        vb[k][j] = 0;
                        vb[j][k] = 1;
                    }
                }
                used[j] = 1;
//                vec2[i+1][j] = vec2[i][0] + vec2[i][1] + vec2[i][2] +
//                    vec2[i][3] + vec2[i][4] + vec2[i][5] + 
//                    (vec2[i][j].a == 0); //do poprawy
                    //jednak nie poprawy, do reworka
            }
        }
//        cout << " - - - - \n";
        modular sum2{0};
//        for(auto& x : vec2)
//        {
            for(auto y : vec2[n])
                sum2 = sum2 + y;
//                cout<<y<<" ";
//            cout<<"\n";
//        }
        if(q)
        {
            int z; char y;
            cin>>z>>y;
            s[z-1] = y;
        }
/*
        for(auto& x : vec2)
        {
            for(auto y : x)
                cout<<y.a<<" ";
            cout<<"\n";
        }
        cout<<" ; ; ; ; ; ; \n";
*/
        cout<<(sum1 - sum2).a<<"\n";
    }
}