文件读写

• 输入文件ribbon.in
• 输出文件ribbon.out

限制

• 1000ms
• 512MB

题目描述

徐老师有一根彩带，这根彩带上一共有 $26$ 种不同的颜色，并且彩带均匀的分割成了长度为 $1$ 的部分，每一块都有一种颜色，为了方便描述颜色，每种颜色用一个小写字母表示

现在徐老师要用这些彩带来组成一根他心目中完美的彩带，于是他先把这根彩带全部剪开，变成了一堆纯色且长度为 $1$ 的彩带片，对于 $a \sim z$ 每种颜色依次有 $a_i$ 片

而徐老师希望得到一根长度为 $n$ 的完美彩带 $s$，完美彩带需要满足两个条件：

1. 首先要保证，组成这根彩带的任意两个相邻的彩带片的颜色满足 $s_i \leq s_{i+1}$
2. 这根完美彩带中必须包含着一个长度为 $m$ 的次完美彩带 $b$（$b_i$ 可以不连续），例如 $b=abcd$，那么对于 $s=abccd,adbdcd$ 都是满足的

现在徐老师想知道，按他手里现有的这些彩带片，他能组合出多少种不同的完美彩带？

由于方案数可能很大，请你将答案对 $1e9+7$ 取模

输入格式

输入第一行包含两个整数 $n,m$，含义如题

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

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

输出格式

输出一个整数，表示徐老师能组合出多少种不同的完美彩带，答案对 $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$ 种