String Formation (Also for AI/ML Software Engineer Intern :)

Take characters from a set of equal-length words to form target, where the chosen column indices are strictly increasing and the same word may be chosen more than once. Ways are distinguished by the chosen columns and the chosen words; different entries of a duplicated word still count as different choices. Output the answer modulo 10⁹+7.

输入格式

The first line contains the number of words n, followed by n lines of words, and the last line contains target. 1≤n≤1000, each word has length 1..3000 and the total length is ≤100000; 1≤target length≤word length; characters are a..z.

输出格式

Output the single integer required by the problem.

样例 1

输入：

3
valya
lyglb
vldoh
val

输出：

4

样例 2

输入：

3
adc
aec
efg
ac

输出：

4

样例 3

输入：

2
aa
aa
aa

输出：

4

样例说明

The answers to the three public examples are, in order: 4; 4; 4. All examples have been verified by independent small-scale enumeration or state search.