CONCAT

You're given a set ~A =~ { ~a_1~, ~...~, ~a_N~ } consisting of ~N~ non-empty strings, all different from each other, composed of lowercase Latin alphabet letters. Also, you're given a non-empty string β in the same alphabet. You are asked to calculate in how many different ways the string β can be produced as a concatenation of any number of strings from the set ~A~. Note that each string from set ~A~ can be used as many times as needed to generate β.

Since the number of different ways can be very large, you're asked to calculate its remainder when divided by ~3.141.592.653.589.793~. (Note that ~32~-bit are not sufficient to represent this number in binary.)

Input

The first line of the input will contain the number ~N~ of strings in set ~A~. The next ~N~ lines will contain the ~N~ strings ~a_1~, ~...~, ~a_N~. The last line will contain the string β. Each line containing a string will consist of one or more consecutive lowercase Latin alphabet letters, without spaces at the beginning, end, or in between, and will end with a newline character.

Output

The output should consist of a single line containing exactly one integer, which is the number of ways the string β can be produced as a concatenation of any number of strings from the set ~A~, modulo ~3.141.592.653.589.793~. If the string β cannot be produced in any way, the output should be ~0~.

Constraints

~1 \le N \le 1.000~.
Each of the strings ~a_1~, ~...~, ~a_N~ will have at most ~1.000~ characters.
The string β will have at most ~1.000.000~ characters.
Execution time limit: 1 sec.
Memory limit: 64 MB.

Examples of Input - Output

1st

STDIN (concat.in)

2
a
b
abaabbb

STDOUT (concat.out)

1

2nd

STDIN (concat.in)

4
a
b
aa
bb
abaabbb

STDOUT (concat.out)

6

3d

STDIN (concat.in)

3
a
aa
aaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

STDOUT (concat.out)

98950096

Explanation

For the given example input ~2~, the ~6~ possible ways to produce the string "~abaabbb~" are:

~a + b + a + a + b + b + b~    ~a + b + a + a + b + bb~    ~a + b + a + a + bb + b~
~a + b + aa + b + b + b~       ~a + b + aa + b + bb~      ~a + b + aa + bb + b~