自动补全

题目背景

现代手机输入法通常会根据用户已经输入的内容显示若干候选词。输入更多字符后，候选范围会逐渐缩小；按下退格键后，一些此前不满足前缀条件的单词又可能重新进入候选栏。

某款手机的自动补全系统还有一条特殊规则：如果上一步操作是退格，系统会优先显示那些刚刚因为这次退格才变得合法的候选词，然后再用原本就合法的候选词补足候选栏。

给定目标单词、按优先级排列的词库、候选栏容量以及操作次数，请计算恰好执行指定次数操作后得到目标单词的方案数。

题目描述

手机键盘包含以下 $27$ 个按键：

• 小写英文字母 a 到 z；
• 退格键。

手机还会显示至多 $S$ 个自动补全建议。

开始时，当前单词为空串。每次操作可以选择以下三种方式之一。

1. 输入一个字母

按下一个字母键，将该字母追加到当前单词末尾。

2. 按下退格键

• 若当前单词非空，删除最后一个字符；
• 若当前单词为空，字符串保持不变。

无论是否真正删除了字符，按下退格键都算作一次操作。

3. 接受自动补全建议

选择当前候选栏中的任意一个单词，将当前单词整体替换为该单词。

接受建议后，仍然可以继续输入字母、按退格键或再次接受建议。

---

词库包含 $N$ 个互不相同的非空字符串：

$$L_1,L_2,\ldots,L_N.$$

词库中的顺序表示优先级：下标越小，优先级越高。

对于当前字符串 $X$，单词 $L_i$ 可以成为合法建议，当且仅当 $X$ 是 $L_i$ 的真前缀，即：

• $L_i$ 以 $X$ 开头；
• $|X|<|L_i|$。

特别地，即使当前字符串 $X$ 本身就在词库中，$X$ 也不会作为自己的自动补全建议。

候选栏按照上一步操作的类型生成。

上一步是输入字母或接受建议

按照词库优先级从高到低，显示前 $S$ 个合法建议。如果合法建议不足 $S$ 个，则全部显示。

在开始操作之前，当前单词为空串，候选栏也按照这一普通规则生成。

上一步是退格

设退格前的字符串为 $Y$，退格后的当前字符串为 $X$。候选栏分两轮构造：

1. 按词库优先级，选择至多 $S$ 个满足以下条件的单词：
   • $X$ 是该单词的真前缀；
   • $Y$ 不是该单词的真前缀。
2. 如果候选数仍不足 $S$，再按词库优先级加入满足“$Y$ 是其真前缀”的单词，直到候选数达到 $S$，或没有更多合法单词。

如果在空串上按下退格键，则 $X=Y$ 均为空串。此时第一轮不会加入任何单词，第二轮按照词库优先级选择普通候选词。

给定目标字符串 $W$ 和操作次数 $A$，求恰好执行 $A$ 次操作后，当前单词恰好等于 $W$ 的操作序列数量。

答案对

$$10^9+7$$

取模。

中途产生的字符串没有任何限制：

• 可以在第 $A$ 次操作之前多次得到 $W$；
• 可以输入不在 $W$ 中的字符；
• 可以产生比词库中所有单词都更长的字符串。

输入格式

第一行包含目标字符串 $W$。$W$ 可能为空串；当 $W$ 为空串时，第一行就是一个空行。

第二行包含一个整数 $N$，表示词库大小。

接下来 $N$ 行，第 $i$ 行包含字符串 $L_i$。输入顺序就是词库优先级顺序。

最后一行包含两个整数 $S,A$，分别表示候选栏最多显示的建议数量和操作次数。

输出格式

输出一行一个整数，表示恰好执行 $A$ 次操作后得到 $W$ 的方案数，对 $10^9+7$ 取模后的结果。

样例 1

输入

topcoder
0
1 7

输出

0

解释

目标单词长度为 $8$，而只有 $7$ 次操作，并且词库为空，因此无法完成。

样例 2

输入

topcoder
0
3 8

输出

1

解释

唯一方案是依次输入 topcoder 的八个字母。

样例 3

输入

topcoder
8
tamale
tester
torus
tomato
top
topcat
topper
topcoder
3 4

输出

2

解释

两种合法方案为：

1. 输入 t、o、p，然后接受建议 topcoder；
2. 输入 t、o，接受建议 top，再接受建议 topcoder。

样例 4

输入

topcoder
4
topher
topcat
topper
topcoder
3 4

输出

1

解释

唯一方案是：接受建议 topcat，连续按两次退格，再接受建议 topcoder。

第一次退格后，当前字符串从 topcat 变为 topca，此时 topcoder 还不是合法建议。第二次退格后，当前字符串变为 topc，topcoder 因这次退格才首次成为合法建议，因此会在第一轮中被优先加入候选栏。

样例 5

本样例的目标字符串为空串，因此输入的第一行是空行。

输入

0
1 14

输出

60432638

解释

实际方案数很大，输出其对 $10^9+7$ 取模后的结果。

数据范围

对于全部测试数据：

$$0\le |W|\le 50;$$ $$0\le N\le 50;$$ $$1\le |L_i|\le 50;$$ $$\sum_{i=1}^{N}|L_i|\le 1000;$$ $$1\le S\le 5;$$ $$1\le A\le 50.$$

此外：

• $W$ 和所有 $L_i$ 仅包含小写英文字母；
• 所有 $L_i$ 互不相同。