3909: 张老师的完美彩带
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
张老师有一根彩带，这根彩带上一共有 $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$ 取模
现在张老师要用这些彩带来组成一根他心目中完美的彩带，于是他先把这根彩带全部剪开，变成了一堆纯色且长度为 $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$，依次表示次完美彩带的颜色，其中每种颜色用一个小写字母表示
输入第二行包含 $26$ 个整数 $a_i$，依次表示 $a \sim z$ 每种颜色的彩带片数量
输入第三行包含一个字符串 $b$，依次表示次完美彩带的颜色，其中每种颜色用一个小写字母表示
| 测试点编号 | $m \leq$ | 特殊性质 |
| :---: | :---: | :---: |
| $1$ | $1000$ | 只有一个 $a_i$ 不是 $0$ |
| $2$ | $1$ | |
| $3$ | $2$ | |
| $4$ | $1000$ | 只有两个 $a_i$ 不是 $0$ |
| $5$ | $5$ | 所有 $a_i$ 之和小于 $20$ |
| $6$ | $1000$ | 答案小于 $10^9+7$ |
| $7$ | $1000$ | 可能的方案数为 $0$ |
| $8$ | $1000$ | $b$ 序列中存在$b_i > b_{i+1}$ |
| $9 \sim 10$ | $1000$ | |
对于所有数据，有 $1 \leq m \leq n \leq 1000, 1 \leq a_i \leq 10^9$
| :---: | :---: | :---: |
| $1$ | $1000$ | 只有一个 $a_i$ 不是 $0$ |
| $2$ | $1$ | |
| $3$ | $2$ | |
| $4$ | $1000$ | 只有两个 $a_i$ 不是 $0$ |
| $5$ | $5$ | 所有 $a_i$ 之和小于 $20$ |
| $6$ | $1000$ | 答案小于 $10^9+7$ |
| $7$ | $1000$ | 可能的方案数为 $0$ |
| $8$ | $1000$ | $b$ 序列中存在$b_i > b_{i+1}$ |
| $9 \sim 10$ | $1000$ | |
对于所有数据，有 $1 \leq m \leq n \leq 1000, 1 \leq a_i \leq 10^9$
输出
输出一个整数，表示张老师能组合出多少种不同的完美彩带，答案对 $1e9+7$ 取模，若不存在合法方案则输出 $0$
样例输入 复制
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$ 种