题库练习 修复古老的预言
← 上一题 下一题 →

A6962 | 修复古老的预言

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

考古学家在沙漠遗迹中发现了 $N$ 卷残缺的羊皮纸(编号 $0$ 到 $N-1$)。令人惊讶的是,这 $N$ 卷羊皮纸的长度完全相同,且上面密密麻麻地写满了小写英文字母。

根据考古学家的推测,这些羊皮纸中隐藏着一条**终极预言**(目标字符串 $T$)。
修复这条预言的规则非常特殊:
1. 预言 $T$ 的第 $i$ 个字符必须从这 $N$ 卷羊皮纸中的某一个字符提取。
2. 我们必须**从左到右**依次复原预言的字符。
3. 如果预言的第 $i$ 个字符取自某卷羊皮纸的第 $k$ 列,那么预言的第 $i+1$ 个字符必须取自任意一卷羊皮纸的 **第 $k$ 列之后**(即列下标严格大于 $k$)的位置。
4. 你可以重复使用同一卷羊皮纸,只要遵守上述的“列下标严格递增”规则即可。

请你计算一下,有多少种不同的方案可以从这 $N$ 卷羊皮纸中完整地拼凑出预言 $T$?
由于方案数可能非常巨大,请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个整数 $N$ 和 $L$,分别表示羊皮纸的数量和每卷羊皮纸的长度。
接下来 $N$ 行,每行包含一个长度为 $L$ 的字符串,表示羊皮纸的内容。
最后一行包含一个字符串 $T$,表示需要复原的预言目标串。

输出格式

输出一个整数,表示构造预言的方案数(对 $10^9 + 7$ 取模)。

输入输出样例

输入 #1
3 4
acca
bbbb
caca
aba
输出 #1
6
输入 #2
2 4
abba
baab
bab
输出 #2
4
C++ 编辑器
输入
输出