Given n distinct strings S1,S2,...,Sn and a target string T. Count the number of ways to concatenate the strings to form T, where each string can be used multiple times.
### Input
- The first line contains an integer n.
- The next n lines each contain a string Si.
- The next line contains the string T.
### Output
- Print an integer, the number of ways to concatenate modulo 109+7.
### Constraints
- 1≤n≤105.
- 1≤|Si|,|T|≤105.
- 1≤∑|Si|≤5×105.
### Example
Input:
### Example
Input:
3abababab
Output:
4
There are 4 possible concatenations:
- a + b + a + b
- a + b + ab
- ab + a + b
- ab + ab
