P2462 - #2180. 「BJOI2017」魔法咒语

Memory Limit：256 MB Time Limit：1.000 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

Submit Submit Record Statistics ShowOff!

Chandra 是一个魔法天才。

从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。

直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。

根据火之魔法规则，禁咒的构成单位是 $N$ 个基本词汇。施法时只要凝聚精神力，说出一段用这些词语组成的长度恰好等于 $L$ 的语言，就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式，方便施法者以最快语速完成法术。

但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒，因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而，在实际施法时，Chandra 发现有些自创禁咒念出后不但没有预期效果，反而会使自己的精神力迅速枯竭，十分难受。

这个问题令 Chandra 万分不解。她大量阅读典籍，到处走访魔法学者，并且不顾精神折磨一次又一次尝试新咒语，希望找出问题的答案。

很多年过去了，在一次远古遗迹探险中，Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析，神殿应该有上万年的历史，这是极其罕见的。Chandra 小心翼翼地四处探索，沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书，终于解开了多年的困惑。

禁咒法术之所以威力强大，是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 $M$ 个词语，比如情敌的名字、讨厌的植物等等。使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。

例如，若 banana 是唯一的忌讳词语，an、ban、analysis 是基本词汇，禁咒长度须是 $11$ ，则 bananalysis 是无效法术，analysisban、anbanbanban 是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。

谜题破解，Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。

由于答案可能很大，你只需要输出答案模 $10^9+7$ 的结果。

第一行，三个正整数 $LN,\ M,\ L$ 。

接下来 $N$ 行，每行一个只含小写英文字母的字符串，表示一个基本词汇。

接下来 $M$ 行，每行一个只含小写英文字母的字符串，表示一个忌讳词语。

仅一行，一个整数，表示答案（模 $10^9+7$ ）。

样例输入 1

4 2 10
boom
oo
ooh
bang
ob
mo

样例输出 1

样例解释 1

boom/bang/oo
oo/oo/oo/oo/oo
oo/oo/ooh/ooh
oo/ooh/oo/ooh
oo/ooh/ooh/oo
ooh/oo/oo/ooh
ooh/oo/ooh/oo
ooh/ooh/boom
ooh/ooh/oo/oo
ooh/ooh/bang
ooh/bang/ooh
bang/oo/oo/oo
bang/ooh/ooh
bang/bang/oo

样例输入 2

3 1 3
a
ab
aba
aaa

样例输出 2

样例解释 2

有效的禁咒法术有 a/a/ab，a/ab/a，a/aba 共三种。注意，a/ab/a 和 a/aba 算成两种不同的禁咒法术。

样例输入 3

3 1 14
ban
an
analysis
banana

样例输出 3

本题一共有 10 个测试点。下表是每个测试点的数据规模和约定：

测试点编号	$N$	$M$	其它限制
$1$	$= 5$	$= 5$	$L≤10L\le 10$
$2$	$= 10$	$= 1$	$L≤50L\le 50$
$3$	$= 20$	$= 1$	$L≤50L\le 50$
$4$	$= 20$	$= 20$	$L≤100L\le 100$
$5$	$= 40$	$= 10$
$6$	$= 50$	$= 50$
$7$	$= 10$	$= 2$	基本词汇长度不超过 $1$
$8$	$= 26$	$= 10$	基本词汇长度不超过 $1$
$9$	$= 20$	$= 10$	基本词汇长度不超过 $2$
$10$	$= 50$	$= 50$	基本词汇长度不超过 $2$

对于 $100%100\%$ 的数据， $\le N,\ M \le 50$ ， $\le L \le 10^8$ ，基本词汇的长度之和不超过 $100$ ，忌讳词语的长度之和不超过 $100$ 。保证基本词汇不重复，忌讳词语不重复。

2462: #2180. 「BJOI2017」魔法咒语

Description

输入格式

输出格式

样例