intPow(int a, int b){ int res = 1; while (b) { if (b & 1)res = 1ll * res * a % mod; b >>= 1; a = 1ll * a * a % mod; } return res; }
char s[N];
structQ { int op, p; char c;
booloperator<(const Q &b) const { return p == b.p ? op < b.op : p < b.p; } } qq[510];
structMat { int a[N][N]; int r, c;
Mat(int _r = N, int _c = N) { r = _r, c = _c; for (int i = 0; i < r; i++)for (int j = 0; j < c; j++)a[i][j] = 0; }
Mat operator*(Mat b) const { Mat ans(r, b.c); for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) if (a[i][j]) for (int k = 0; k < b.c; ++k)ans.a[i][k] = (ans.a[i][k] + 1ll * a[i][j] * b.a[j][k]) % mod; return ans; } } A, ans, B, pw[40];
int tot = 1, nw[40];
voidpow(int n){ for (int i = 0; i <= 30; i++) { if (n >> i & 1)ans = ans * pw[i], tot = 1ll * tot * nw[i] % mod; } }
int fail[N], trans[N][30]; //fail即KMP中nxt,trans表示从第i位经过字符j转移到的位置
voidbuild(char *s){ int n = strlen(s + 1); fail[0] = 0, fail[1] = 0; trans[0][s[1] - 'a'] = 1, trans[1][s[2] - 'a'] = 2; for (int i = 2, j = 0; i <= n; i++) { while (j && s[j + 1] != s[i])j = fail[j]; fail[i] = j = (s[j + 1] == s[i] ? j + 1 : j); if (i < n)trans[i][s[i + 1] - 'a'] = i + 1; } for (int i = 0; i <= n; i++) { for (int j = 0; j < 26; j++) { if (!trans[i][j])trans[i][j] = trans[fail[i]][j]; } } }
int ck[30];
intmain(){ scanf("%d%d%d", &n, &m, &q); scanf("%s", s + 1); build(s); for (int i = 1; i <= q; i++) { scanf("%d%d", &qq[i].op, &qq[i].p); scanf(" %c", &qq[i].c); } ans = Mat(1, n + 2); A = Mat(n + 2, n + 2); sort(qq + 1, qq + q + 1); ans.a[0][0] = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j < 26; j++) { A.a[i][trans[i][j]]++; } } for (int i = 0; i <= n; i++)A.a[i][n + 1] = A.a[i][n]; A.a[n + 1][n + 1] = 26; pw[0] = A; for (int i = 1; i <= 30; i++)pw[i] = pw[i - 1] * pw[i - 1]; nw[0] = 26; for (int i = 1; i <= 30; i++)nw[i] = 1ll * nw[i - 1] * nw[i - 1] % mod; for (int i = 1, las = 0, r; i <= q; i = r) { B = Mat(n + 2, n + 2); int p = qq[i].p; pow(p - las - 1); las = p; r = i; for (int j = 0; j < 26; j++)ck[j] = 1; while (r <= q && qq[r].p == qq[i].p) { if (qq[r].op == 0)ck[qq[r].c - 'a'] = 0; else { for (int j = 0; j < 26; j++)if (j != qq[r].c - 'a')ck[j] = 0; } r++; } for (int j = 0; j <= n; j++) { for (int k = 0; k < 26; k++) { if (ck[k])B.a[j][trans[j][k]]++; } } int cnt = 0; for (int j = 0; j < 26; j++)if (ck[j])cnt++; for (int j = 0; j <= n; j++)B.a[j][n + 1] = B.a[j][n]; B.a[n + 1][n + 1] = cnt; ans = ans * B; tot = 1ll * tot * cnt % mod; } pow(m - qq[q].p); printf("%lld\n", 1ll * ans.a[0][n + 1] * Pow(tot, mod - 2) % mod); return0; }