#216297. [蓝桥杯 2026 省 A] 基因研究

DNA 分子的四种碱基分别记为 A、T、G、C。每个人的基因序列都可以认为是一个由 A、T、G、C 四种字符组成的长度为 的字符串。

小蓝正在研究一种疾病。他观察到，这种疾病存在一个固定的易感序列（也可认为是一个由 A、T、G、C 构成的字符串）。若某人的基因序列中存在一个子串恰好等于这个易感序列，则称此人“易感”；若基因序列的任意子串都不等于这个易感序列，则称此人“不易感”。

小蓝希望根据这座城市中人们的基因序列情况，估计出城里“易感”人群所占的比例。

然而，直接获取整座城市中每个人完整的基因序列非常困难。为此，小蓝采用了抽样统计的方法：通过大量采样，他估计出了在这座城市中，每一个位置上碱基为 A、T、G、C 的人数占比。我们可以将其理解为：在所有人的基因序列中，第 个位置为 A、T、G、C 的人数占比分别是多少。

为了简化模型，小蓝作出如下假设：对于任意一个人，其基因序列在每个位置上的碱基分布与采样结果完全一致，且不同位置之间的碱基相互独立。也就是说，即使已经确定了若干个位置上的碱基，剩余位置上的碱基仍然按照对应位置的分布独立生成。

现在，小蓝决定将这些概率以模 的形式算出：如果“易感”人群所占比例为 ，则小蓝希望得到一个整数 ，满足 。请你根据给定的易感序列，以及每个位置上四种碱基的概率分布，帮小蓝计算并输出这个整数 。

第一行包含两个正整数 ，分别表示基因序列长度和易感序列长度。

第二行包含一个长度为 的字符串 ，仅由 A、T、G、C 构成，表示疾病对应的易感序列。

接下来 行，每行包含四个非负整数 。其中：

• 表示第 个位置碱基为 A 的概率（模 意义下）；
• 表示第 个位置碱基为 T 的概率（模 意义下）；
• 表示第 个位置碱基为 G 的概率（模 意义下）；
• 表示第 个位置碱基为 C 的概率（模 意义下）。

保证对任意 ，均有 。

输出一行，包含一个非负整数，表示“基因序列中包含易感序列作为子串”的人群占比在模 意义下的结果。

样例输入 1

3 2
AA
499122177 499122177 0 0
499122177 0 499122177 0
499122177 0 0 499122177

样例输出 1

623902721

【样例说明】

基因序列共有 个位置：

• 第 位有 的概率是 ，有 的概率是 ；
• 第 位有 的概率是 ，有 的概率是 ；
• 第 位有 的概率是 ，有 的概率是 。

易感序列为 。因此，一个人被视为“易感”，当且仅当其基因序列中包含子串 。

所有可能产生的基因序列中，满足条件的共有 3 种，分别是 、 和 。这 3 种序列出现的概率均为 ，因此“易感”人群所占的总比例为 ，其在模 意义下的结果为 。

【评测用例规模与约定】

对于 的数据，；

另存在 的数据，；

对于 的数据，。