小核桃有一个长度为 $n$ 的字符串 $s$，$s$ 仅包含小写字母，且对于任意的 $i(1 \leq i < n)$ 有 $s_i \leq s_{i+1}$，即字符串的内容是递增的。

而且字符串每个字母都有使用次数限制。现在小核桃只记得密码串的一个子序列和原密码串的长度，你能帮他算出原密码串有多少种可能吗？由于答案可能很大，请输出答案对 $10^9+7$ 求余之后的结果。

输入格式

输入第一行包括两个整数 $n,k$，表示小核桃字符串子序列的长度和原字符串的长度

输入第二行包括 $26$ 个数 $a_i$ $(0\le a_i\le 10^9)$ 代表 $\texttt{a}$ 到 $\texttt{z}$ 中每个字母的出现次数限制。

输入第三行包括一个长度为 $n$ 的字符串 $s$，字符串只包括小写字母。

输出格式

输出一行一个数字表示答案对 $10^9+7$ 求余的结果，如果可能的方案数为 0，输出 NO SOLUTION!。

4 5
1 1 4 5 1 4 1 9 1 9 8 1 0 1 1 4 5 1 4 1 9 1 9 8 1 0
abcd

22

说明

可能是 abccd, 或者 abcd$*$。

$*$ 表示除了 $a,b,c,m,z$ 之外的 21 种字母，这些字符串都是可以的。所以总共有 22 种字符串。

测试点说明

对于所有数据，有 $1 \leq n \leq k \leq 1000$