DNA 分子的四种碱基分别记为 A、T、G、C。每个人的基因序列都可以认为是一个由 A、T、G、C 四种字符组成的长度为 n 的字符串。
小蓝正在研究一种疾病。他观察到，这种疾病存在一个固定的易感序列（也可认为是一个由 A、T、G、C 构成的字符串）。若某人的基因序列中存在一个子串恰好等于这个易感序列，则称此人“易感”；若基因序列的任意子串都不等于这个易感序列，则称此人 “不易感”。
小蓝希望根据这座城市中人们的基因序列情况，估计出城里 “易感” 人群所占的比例。然而，直接获取整座城市中每个人完整的基因序列非常困难。为此，小蓝采用了抽样统计的方法：通过大量采样，他估计出了在这座城市中，每一个位置上碱基为 A、T、G、C 的人数占比。我们可以将其理解为：在所有人的基因序列中，第 i 个位置为 A、T、G、C 的人数占比分别是多少。
为了简化模型，小蓝作出如下假设：对于任意一个人，其基因序列在每个位置上的碱基分布与采样结果完全一致，且不同位置之间的碱基相互独立。也就是说，即使已经确定了若干个位置上的碱基，剩余位置上的碱基仍然按照对应位置的分布独立生成。
现在，小蓝决定将这些概率以模 998244353 的形式算出：如果 “易感” 人群所占比例为 pq ，则小蓝希望得到一个整数 x，满足 x × q ≡ p (mod 998244353)。
请你根据给定的易感序列，以及每个位置上四种碱基的概率分布，帮小蓝计算并输出这个整数 x。
第一行包含两个正整数 n, m，分别表示基因序列长度和易感序列长度。
第二行包含一个长度为 m 的字符串 s，仅由 A、T、G、C 构成，表示疾病
对应的易感序列。
接下来 n 行，每行包含四个非负整数 ai, ti, gi, ci。其中：
• ai 表示第 i 个位置碱基为 A 的概率（模 998244353 意义下）；
• ti 表示第 i 个位置碱基为 T 的概率（模 998244353 意义下）；
• gi 表示第 i 个位置碱基为 G 的概率（模 998244353 意义下）；
• ci 表示第 i 个位置碱基为 C 的概率（模 998244353 意义下）。
保证对任意 i，均有 (ai + ti + gi + ci) mod 998244353 = 1。
输出一行，包含一个非负整数，表示“基因序列中包含易感序列作为子串”的人群占比在模 998244353 意义下的结果。
3 2 AA 499122177 499122177 0 0 499122177 0 499122177 0 499122177 0 0 499122177
623902721
【样例说明】
基因序列共有 3 个位置：
• 第 1 位有 1/2 的概率是 A，有 1/2 的概率是 T；
• 第 2 位有 1/2 的概率是 A，有 1/2 的概率是 G；
• 第 3 位有 1/2 的概率是 A，有 1/2 的概率是 C。
易感序列为 AA。因此，一个人被视为“易感”，当且仅当其基因序列中包含子串 AA。
所有可能产生的基因序列中，满足条件的共有 3 种，分别是 AAC、TAA和 AAA。这 3 种序列出现的概率均为 1/8，因此“易感”人群所占的总比例为1/8 + 1/8 + 1/8 = 3/8，其在模 998244353 意义下的结果为 623902721。
【评测用例规模与约定】
对于 30% 的数据，1 ≤ m ≤ n ≤ 5；
另存在 20% 的数据，ai = ti = gi = ci；
对于 100% 的数据，1 ≤ m ≤ n ≤ 3000, 0 ≤ ai, ti, gi, ci < 998244353。