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

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2")
#define int long long

using namespace std;
// using LL = long long;
// #define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
// #define REP(i, n) FOR(i, 0, (n) - 1)
// #define ssize(x) int(x.size())
#define MOD 998244353

int odp(string &s)
{
	vector<int> mp(256, -1);

	int n = s.size();
	int allCount = 0, levelCount = 0;

	vector<int> last_reps(256, 0);
	int total_reps = 0;

	for (int i = 0; i < n; i++)
	{
		char c = s[i];

		if (i == 0)
		{
			allCount = levelCount = 1;
			mp[c] = 1;
			continue;
		}

		levelCount = allCount + 1;

		if (mp[c] == -1)
		{
			total_reps *= 2;
			allCount += levelCount;
		}
		else
		{
			allCount += levelCount - mp[c];
			total_reps += mp[c] - last_reps[c];
			last_reps[c] = mp[c] % MOD;
			// cerr << "I" << total_reps << "bo mp = " << mp[c] << endl;
		}
		mp[c] = levelCount % MOD;

		allCount %= MOD;
		total_reps += MOD;
		total_reps %= MOD;
	}

	return total_reps;
}

int32_t main()
{
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	cout << odp(s) << endl;
	for (int i = 0; i < q; i++)
	{
		int pos;
		char c;
		cin >> pos >> c;
		pos--;
		s[pos] = c;
		cout << odp(s) << endl;
	}
	return 0;
}