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
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <time.h>
#include <queue>
#include <cmath>
#include <string>

using namespace std;

const int64_t MOD = 998244353LL;

void naive(int n, int q, vector<char>& word) {
	for (int i = 0; i <= q; ++i) {
		int p2n = pow(2, n);
		if (i > 0) {
			int pos;
			char c;
			scanf("%d %c", &pos, &c);
			word[pos - 1] = c;
		}
		map<string, int64_t> subwords;
		for (int i = 0; i < p2n; ++i) {
			string sw = "";
			int idx = 1;
			for (int j = 0; j < n; ++j) {
				if (i & idx) {
					sw += word[j];
				}
				idx <<= 1;
			}
			if (subwords.find(sw) == subwords.end()) {
				subwords[sw] = 1;
			}
			else {
				subwords[sw]++;
			}
		}
		int64_t cnt = 0;
		for (map<string, int64_t>::iterator it = subwords.begin(); it != subwords.end(); it++) {
			if (it->second > 1) {
				cnt = (cnt + 1) % MOD;
			}
		}
		printf("%lld\n", cnt);
	}
}

int main () {
	int n, q;
	scanf("%d %d\n", &n, &q);
	vector<char> word;
	word.reserve(n + 8);
	bool ab_only = true;
	for (int i = 0; i < n; ++i) {
		char c;
		scanf("%c", &c);
		word.push_back(c);
		if (c > 'b') {
			ab_only = false;
		}
	}
	if (!ab_only) {
		naive(n, q, word);
		return 0;
	}
	vector<int64_t> distinct(n + 8, 0);
	distinct[0] = 1;
	vector<int> last(255, -1);
	vector<int64_t> fib;
	fib.reserve(n + 16);
	fib.push_back(0);
	fib.push_back(1);
	for (int i = 2; i < n + 8; ++i) {
		fib.push_back((fib[i - 2] + fib[i - 1]) % MOD);
	}
	fib[3]--;
	for (int i = 0; i <= q; ++i) {
		if (i > 0) {
			int pos;
			char c;
			scanf("%d %c", &pos, &c);
			word[pos - 1] = c;
		}
		for (char c = 'a'; c <= 'f'; ++c) {
			last[c] = -1;
		}
		int changes = 0;
		for (int j = 1; j <= n; ++j) {
			if (j < n && word[j] != word[j - 1]) {
				++changes;
			}
			distinct[j] = distinct[j - 1] << 1;
			if (last[word[j - 1]] != -1) {
				distinct[j] -= distinct[last[word[j - 1]]];
			}
			distinct[j] %= MOD;
			last[word[j - 1]] = j - 1;
		}
//		printf("DISTINCT %lld CHANGES %d\n", distinct[n], changes);
		printf("%lld\n", (3 * MOD + distinct[n] - fib[changes + 3] - 1) % MOD);
	}
	return 0;
}