测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6962. 修复古老的预言

编程题 普及+/提高

题目描述

考古学家在沙漠遗迹中发现了 $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

说明/提示

## 样例解释与数据范围

### 样例 #1 解释
羊皮纸内容:
- 0: acca
- 1: bbbb
- 2: caca
目标:aba

我们可以这样构造(列下标从 0 开始):
1. aba -> 第 0 列('a' from 0), 第 1 列('b' from 1), 第 3 列('a' from 0)
2. aba -> 第 0 列('a' from 0), 第 1 列('b' from 1), 第 3 列('a' from 2)
3. aba -> 第 0 列('a' from 0), 第 2 列('b' from 1), 第 3 列('a' from 0)
4. aba -> 第 0 列('a' from 0), 第 2 列('b' from 1), 第 3 列('a' from 2)
5. aba -> 第 1 列('a' from 2), 第 2 列('b' from 1), 第 3 列('a' from 0)
6. aba -> 第 1 列('a' from 2), 第 2 列('b' from 1), 第 3 列('a' from 2)
共 6 种。

### 数据范围

- $1 \le N \le 1000$ (羊皮纸数量)
- $1 \le L \le 1000$ (羊皮纸长度)
- $1 \le |T| \le 1000$ (目标串长度)
- 所有字符均为小写英文字母。

**数据点分布:**
- 测试点 1-5:$L, |T| \le 10$
- 测试点 6-15:$L, |T| \le 100$
- 测试点 16-25:$L, |T| \le 1000$
上一题 去做题 下一题