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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=998244353;
const int LIM=5e4+7;
ll trile[4*LIM][49], truni[4*LIM][6][6], trma[4*LIM][6], trmi[4*LIM][6], P[7][49], N=1;
void cop(ll *A, ll *B) {
	rep(i, 49) B[i]=A[i];
}
void mult(ll *A, ll *B, ll *C) {
	rep(i, 7) rep(j, 7) {
		C[i*7+j]=0;
		rep(k, 7) C[i*7+j]=(C[i*7+j]+A[i*7+k]*B[k*7+j])%MOD;
	}
}
void cnt(int v) {
	mult(trile[2*v], trile[2*v+1], trile[v]);
	rep(i, 6) {
		trma[v][i]=max(trma[2*v][i], trma[2*v+1][i]);
		trmi[v][i]=min(trmi[2*v][i], trmi[2*v+1][i]);
	}
	rep(i, 6) rep(j, 6) {
		truni[v][i][j]=0;
		if(trmi[2*v+1][j]==MOD) truni[v][i][j]=(truni[v][i][j]+truni[2*v][i][j])%MOD;
		if(trma[2*v][i]==-MOD) truni[v][i][j]=(truni[v][i][j]+truni[2*v+1][i][j])%MOD;
		rep(a, 6) rep(b, 6) {
			if(trma[2*v][b]<=trma[2*v][a] && trmi[2*v+1][a]>=trmi[2*v+1][b]) truni[v][i][j]=(truni[v][i][j]+truni[2*v][i][a]*truni[2*v+1][b][j])%MOD;
		}
	}
}
void ustaw(int v, int x) {
	cop(P[x], trile[v]);
	rep(i, 6) {
		rep(j, 6) truni[v][i][j]=0;
		trma[v][i]=-MOD;
		trmi[v][i]=MOD;
	}
	trmi[v][x]=trma[v][x]=v;
	truni[v][x][x]=1;
}
void upd(int v, int x) {
	v+=N;
	ustaw(v, x);
	v/=2;
	while(v) {
		cnt(v);
		v/=2;
	}
}
ll liczile() {
	return trile[1][48];
}
ll liczuni() {
	ll ans=1;
	rep(i, 6) rep(j, 6) ans=(ans+truni[1][i][j])%MOD;
	return ans;
}
ll licz() {
	return (liczile()-liczuni()+MOD)%MOD;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int los(int a, int b) {
	return rng()%(b-a+1)+a;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	rep(i, 7) P[6][8*i]=1;
	rep(i, 6) {
		rep(j, 6) if(i!=j) P[i][8*j]=1;
		P[i][48]=2;
		P[i][6*7+i]=1;
		P[i][i*7+6]=MOD-1;
	}
	int n, q;
	string s;
	cin >> n >> q >> s;
	while(N<n) N*=2;
	rep(i, 2*N) {
		cop(P[6], trile[i]);
		rep(a, 6) {
			rep(b, 6) truni[i][a][b]=0;
			trma[i][a]=-MOD;
			trmi[i][a]=MOD;
		}
	}
	rep(i, n) ustaw(N+i, s[i]-'a');
	for(int i=N-1; i; --i) cnt(i);
	cout << licz() << '\n';
	while(q--) {
		int a;
		char b;
		cin >> a >> b; --a;
		upd(a, b-'a');
		cout << licz() << '\n';
	}
}