A94822.修复古老的预言
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
考古学家在沙漠遗迹中发现了 N 卷残缺的羊皮纸(编号 0 到 N−1)。令人惊讶的是,这 N 卷羊皮纸的长度完全相同,且上面密密麻麻地写满了小写英文字母。
根据考古学家的推测,这些羊皮纸中隐藏着一条终极预言(目标字符串 T)。
修复这条预言的规则非常特殊:
- 预言 T 的第 i 个字符必须从这 N 卷羊皮纸中的某一个字符提取。
- 我们必须从左到右依次复原预言的字符。
- 如果预言的第 i 个字符取自某卷羊皮纸的第 k 列,那么预言的第 i+1 个字符必须取自任意一卷羊皮纸的 第 k 列之后(即列下标严格大于 k)的位置。
- 你可以重复使用同一卷羊皮纸,只要遵守上述的“列下标严格递增”规则即可。
请你计算一下,有多少种不同的方案可以从这 N 卷羊皮纸中完整地拼凑出预言 T?
由于方案数可能非常巨大,请输出答案对 109+7 取模后的结果。
输入格式
第一行包含两个整数 N 和 L,分别表示羊皮纸的数量和每卷羊皮纸的长度。
接下来 N 行,每行包含一个长度为 L 的字符串,表示羊皮纸的内容。
最后一行包含一个字符串 T,表示需要复原的预言目标串。
输出格式
输出一个整数,表示构造预言的方案数(对 109+7 取模)。
输入输出样例
输入#1
3 4 acca bbbb caca aba
输出#1
6
输入#2
2 4 abba baab bab
输出#2
4
说明/提示
样例解释与数据范围
样例 #1 解释
羊皮纸内容:
- 0:
acca - 1:
bbbb - 2:
caca
目标:aba
我们可以这样构造(列下标从 0 开始):
aba-> 第 0 列('a' from 0), 第 1 列('b' from 1), 第 3 列('a' from 0)aba-> 第 0 列('a' from 0), 第 1 列('b' from 1), 第 3 列('a' from 2)aba-> 第 0 列('a' from 0), 第 2 列('b' from 1), 第 3 列('a' from 0)aba-> 第 0 列('a' from 0), 第 2 列('b' from 1), 第 3 列('a' from 2)aba-> 第 1 列('a' from 2), 第 2 列('b' from 1), 第 3 列('a' from 0)aba-> 第 1 列('a' from 2), 第 2 列('b' from 1), 第 3 列('a' from 2)
共 6 种。
数据范围
- 1≤N≤1000 (羊皮纸数量)
- 1≤L≤1000 (羊皮纸长度)
- 1≤∣T∣≤1000 (目标串长度)
- 所有字符均为小写英文字母。
数据点分布:
- 测试点 1-5:L,∣T∣≤10
- 测试点 6-15:L,∣T∣≤100
- 测试点 16-25:L,∣T∣≤1000