题目描述

强哥最近发现了一箱神奇的彩带，这些彩带可是幼儿园的宝贝！它们共有 26 种不同的颜色，每条彩带都被切成了整齐的小段，每一段都是纯色的。为了方便记住这些颜色，强哥用 a 到 z 这 26 个字母来代表这些颜色。

但是，强哥是个追求完美的人！他觉得这些彩带还远远不够好看，于是他拿起剪刀，“咔嚓咔嚓”把彩带全剪开，变成了一堆单色的彩带片。每种颜色的彩带片，强哥都数得一清二楚，比如 a 颜色有 $a_i$ 片，b 颜色有 $b_i$ 片……

接下来，强哥想按照他心目中的标准，重新拼出一根长度为 $n$ 的“完美彩带”！他的 “完美彩带 $S$” 必须满足两个重要的条件：

1. 这根彩带的颜色必须越来越“有序”，简单来说，颜色是不能“乱来”的，也就是任意相邻的彩带片都得满足 $S_i \leq S_{i+1}$，强哥绝不允许前面彩带比后面的颜色还大，必须是从小到大排！
2. 彩带必须藏着一个“小彩蛋”——在这根“完美彩带”里，一定要包含一段长为 $m$ 的 “次完美彩带” $b$，虽然它可以不连续，但它必须完整地出现在彩带里。比如，如果 $b=abcd$（次完美彩带为 $abcd$），那么像 $S=abccd$ 或者 $S=abbbcd$ 这种彩带，强哥都觉得够完美。

现在，强哥坐在一大堆彩带片中间，抓耳挠腮地想着：到底有多少种不同的“完美彩带”可以拼出来呢？

由于可能的拼接方案太多了，强哥的脑袋要“爆炸”了！他赶紧求助你来帮忙计算一下，并且把答案对 $1e9+7$ 取模，别让数字太大哟。

输入格式 (d.in)

输入第一行包含两个整数 $n,m$，$n$ 表示完美彩带的长度，$m$ 表示次完美彩带的长度。

输入第二行包含 $26$ 个整数 $a_i$，依次表示 $a \sim z$ 每种颜色的彩带片数量

输入第三行包含一个字符串 $b$，依次表示次完美彩带的颜色，其中每种颜色用一个小写字母表示

输出格式 (d.out)

输出一个整数，表示强哥能组合出多少种不同的完美彩带，答案对 $1e9+7$ 取模，若不存在合法方案则输出 $0$

数据范围

对于所有数据，有 $1 \leq m \leq n \leq 1000, 1 \leq a_i \leq 10^9$

样例输入

6 4
1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 9
abcd

样例输出

277

样例解释

可能的方案为

1. $abccd$ 后拼接 $d \sim z$ 中的任意一个字符，方案为 $23$ 种
2. $abcdd$ 后拼接 $e \sim z$ 中的任意一个字符，方案为 $22$ 种
3. 同 $2$ 号方案，$abcde \sim abcdy$ 依次有 $21+20+19+ \dots 1 =231$ 种
4. $abcdzz$ 一种

共计方案 $23+22+231+1=277$ 种