A94822.修复古老的预言

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

根据考古学家的推测,这些羊皮纸中隐藏着一条终极预言(目标字符串 TT)。
修复这条预言的规则非常特殊:

  1. 预言 TT 的第 ii 个字符必须从这 NN 卷羊皮纸中的某一个字符提取。
  2. 我们必须从左到右依次复原预言的字符。
  3. 如果预言的第 ii 个字符取自某卷羊皮纸的第 kk 列,那么预言的第 i+1i+1 个字符必须取自任意一卷羊皮纸的 kk 列之后(即列下标严格大于 kk)的位置。
  4. 你可以重复使用同一卷羊皮纸,只要遵守上述的“列下标严格递增”规则即可。

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

输入格式

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

输出格式

输出一个整数,表示构造预言的方案数(对 109+710^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 种。

数据范围

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

数据点分布:

  • 测试点 1-5:L,T10L, |T| \le 10
  • 测试点 6-15:L,T100L, |T| \le 100
  • 测试点 16-25:L,T1000L, |T| \le 1000
首页