题目描述

NIT 在 $n$ 年前还是普及组选手的时候做过这样一个题目，求一个字符串在另一个字符串中出现了几次，以 NIT 现在国家队的实力，做这样的题实在是太侮辱他的智商了，于是他思考着加强这道题目。

给定一个长度为 $n$ 的字符串，求这个字符串在满足要求的长度为 $m$ 的小写字符串中的期望出现次数。对 $998244353$ 取模。

输入格式

输入共 $k+2$ 行。

第一行三个非负整数表示 $n,m,k$。$k$ 表示限制数。

第二行一个长度为 $n$ 的字符串，仅包含小写字母，为给定字符串。

第 $3$ 至第 $k+2$ 行，每行两个整数 $opt,x$ 和一个小写字母 $ch$。

若 $opt=0$，则要求第 $x$ 个字符不为 $ch$。

若 $opt=1$，则要求第 $x$ 个字符必须为 $ch$。

输出格式

一行一个非负整数表示答案对 $998244353$ 取模的值。

样例

样例输入 1

2 3 0
aa

样例输出 1

286478409

样例 1 解释

aa 共出现了 $52$ 次，注意在 aaa 中是算出现了 $2$ 次，总共有 $17576$ 个合法串。故期望为 $\dfrac{1}{338}$。

样例输入 2

2 4 1
aa
1 1 a

样例输出 2

17720314

数据范围

所有数据满足：$1\leqslant n \leqslant 100,1\leqslant k \leqslant 500 ,1\leqslant n\leqslant m \leqslant 10^9,1\leqslant x\leqslant m$。