问题陈述
给你一个字符串 $t$ 和一组 $S$ 的 $N$ 不同字符串。您需要分隔 $t$,以便每个部分都包含在 $S$ 中。
例如,以下4种分离方法满足$t = abab$且$S = \{a, ab, b\}$时的条件。
- $a、b、a、b$
- $a、b、ab$
- $ab、a、b$
- $ab, ab$
你的任务是计算分隔 $t$ 的方法的数量。由于结果可能很大,因此您应该输出除以 $1{,}000{,}000{,}007$ 的余数。
输入
输入由单个测试用例组成,格式如下。
$N$ $s_1$ $\vdots$ $s_N$ $t$
第一行由一个整数 $N \ (1 \le N \le 100{,}000)$ 组成,它是 $S$ 的元素数量。 以下 $N$ 行由 $N$ 个由换行符分隔的不同字符串组成。第 $i$ 个字符串 $s_i$ 表示 $S$ 的第 $i$ 个元素。 $s_i$ 由小写字母组成,长度在 $1$ 到 $100{,}000$(含)之间。 $s_{i} \ (1 \le i \le N)$ 的长度总和最多为 $200{,}000$。 下一行是字符串$t$,由小写字母组成,表示要分隔的字符串,长度在$1$到$100{,}000$(含)之间。
输出
计算分隔 $t$ 的方法数,并打印除以 $1{,}000{,}000{,}007$ 所得的余数。
样本输入 1
3 a b ab abab
样本输入 1 的输出
4
示例输入 2
3 a b c xyz
样本输入 2 的输出
0
示例输入 3
7 abc ab bc a b c aa aaabcbccababbc
样本输入 3 的输出
160
示例输入 4
10 a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
样本输入 4 的输出
461695029