题目描述

给定一个字符串 $t$ 和一个包含 $N$ 个不同字符串的集合 $S$，你需要将 $t$ 分割成若干部分，使得每一部分都包含在 $S$ 中。

例如，当 $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$ 行中，每行包含一个不同的字符串，用换行符分隔。第 $i$ 个字符串 $s_i$ 表示 $S$ 的第 $i$ 个元素。$s_i$ 由小写字母组成，长度在 $1$ 到 $100{,}000$ 之间（包含边界）。$s_i$ 的长度之和 $\sum 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