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

using namespace std;
typedef long long ll;
const ll MOD=998244353;

ll calcAns(string& s)
{
	vector<ll> dp1(6,0); //wystepujace dokladnie raz
	vector<int> last(6,-1);
	vector<ll> dp2(6,0); //wszystkie rozne
	dp1[s[0]-'a']=1;
	dp2[s[0]-'a']=1;
	last[s[0]-'a']=0;
	ll All1=0, All2=2;
	int n=s.size();
	for(int i=1;i<n;i++){
		ll tv=0;
		for(int j=0;j<6;j++){
			if(last[j] >= last[s[i]-'a']) tv+=dp1[j];
		}
		if(last[s[i]-'a']==-1) tv++;
		dp1[s[i]-'a']=tv;
		dp1[s[i]-'a']%=MOD;
		last[s[i]-'a']=i;
		
		ll nw2=All2;
		All2*=2;
		All2=(All2-dp2[s[i]-'a']+MOD)%MOD;
		dp2[s[i]-'a']=nw2;
	}
	for(int i=0;i<6;i++) All1+=dp1[i];
	All1%=MOD;
	return (All2 - 1 - All1 + MOD) % MOD;
}

void solve()
{
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	cout << calcAns(s) << "\n";
	for(int i=0;i<q;i++){
		int pos;
		char z;
		cin >> pos >> z;
		pos--;
		s[pos]=z;
		cout << calcAns(s) << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	
	return 0;
}