G. Secret Words
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sirin has moved to a parallel world, and the Fairy Patrol needs to go after him.

Snezka approached the old fireplace and noticed that a corner of some old scroll was sticking out from behind a brick. She carefully pulled it out and unfolded it. The parchment was filled with a continuous stream of incomprehensible letters and symbols, and next to it lay a small sheet with a list of mysterious words.

The girls realized that this was yet another cipher from Sirin. At the edge of the sheet was a note — "To those who want to reach the parallel world, you need to break the entire text into separate secret words from this list. Each word can be used any number of times, but nothing extra can be added. Note: the symbols "?" in the text replace any letters of the secret word."

Masha, glancing at the text that Snezka had retrieved, understood that this text could be broken down into words in many ways! How can one find out how many such ways exist? She realized that counting would be necessary. But it seems that the girls themselves cannot handle it — they need your help!

Help the girls from the Fairy Patrol catch up with Sirin — determine how many different ways there are to break the text from the parchment into secret words from the list.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number of secret words.

Each of the following lines contains a string $$$W_i$$$ $$$(1 \le |W_i| \le 10)$$$ — the $$$i$$$-th secret word.

It is guaranteed that all words $$$W_i$$$ are unique, that is, for $$$i \ne j$$$, $$$W_i \ne W_j$$$.

The last line contains a string $$$T$$$ $$$(1 \le |T| \le 100)$$$ — the text from the parchment.

It is guaranteed that

  • each word $$$W_i$$$ consists only of lowercase Latin letters (a — z);
  • the text $$$T$$$ consists only of lowercase Latin letters (a — z) and the symbols "?", where each symbol "?" replaces exactly one arbitrary letter.
Output

Let $$$P$$$ be the number of ways to break the text from the parchment into secret words.

In a single line, output a single integer — the remainder of $$$P$$$ when divided by $$$M = 10^9 + 7$$$.

Examples
Input
7
a
b
c
d
ab
bc
cd
ab?d
Output
11
Input
2
a
b
??
Output
4
Note

First test example

Let's enumerate the possible ways to break the text:

  1. $$$[\texttt{a}, \texttt{b}, \texttt{a}, \texttt{d}]$$$;
  2. $$$[\texttt{a}, \texttt{b}, \texttt{b}, \texttt{d}]$$$;
  3. $$$[\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}]$$$;
  4. $$$[\texttt{a}, \texttt{b}, \texttt{d}, \texttt{d}]$$$;
  5. $$$[\texttt{ab}, \texttt{a}, \texttt{d}]$$$;
  6. $$$[\texttt{ab}, \texttt{b}, \texttt{d}]$$$;
  7. $$$[\texttt{ab}, \texttt{c}, \texttt{d}]$$$;
  8. $$$[\texttt{ab}, \texttt{d}, \texttt{d}]$$$;
  9. $$$[\texttt{a}, \texttt{bc}, \texttt{d}]$$$;
  10. $$$[\texttt{a}, \texttt{b}, \texttt{cd}]$$$;
  11. $$$[\texttt{ab}, \texttt{cd}]$$$.

Second test example

Let's enumerate the possible ways to break the text:

  1. $$$[\texttt{a}, \texttt{a}]$$$;
  2. $$$[\texttt{a}, \texttt{b}]$$$;
  3. $$$[\texttt{b}, \texttt{a}]$$$;
  4. $$$[\texttt{b}, \texttt{b}]$$$.