Chandra is a magic prodigy.
Ever since she was baptized by the Church of Fire at the age of one, Chandra has shown an unparalleled affinity for the fire element, easily mastering all sorts of obscure spells. This is also thanks to her extraordinary linguistic talent, which allows her to fluently pronounce the most tongue-twisting magical terms in incantations.
It was not until she was fourteen and began learning powerful forbidden spells that Chandra encountered an obstacle.
According to the rules of fire magic, a forbidden spell is composed of $N$ basic vocabulary words. When casting a spell, one only needs to focus their mental energy and utter a sequence of these words with a total length exactly equal to $L$ to release fire magic of unimaginable power. Past mages summarized several of the most coherent combinations to allow casters to complete spells at the fastest possible speed.
However, Chandra, a genius in both magic and language, was not satisfied with these traditional forbidden spells, as she could easily pronounce incantations that were nearly impossible for ordinary people. Yet, in actual practice, Chandra discovered that some of her self-created spells not only failed to produce the expected effects but also caused her mental energy to deplete rapidly, which was extremely painful.
This problem puzzled Chandra greatly. She read numerous books, visited magic scholars everywhere, and, despite the mental torment, tried new incantations over and over again, hoping to find the answer.
Many years passed. During an expedition to ancient ruins, Chandra accidentally stumbled into an unknown temple of the Fire God, Alix. Based on geological analysis, the temple is likely over ten thousand years old, which is extremely rare. Chandra explored cautiously and, following the flow of magic, arrived at a secret chamber. She saw a book floating in the center of the room. Protected by magic, the book was in perfect condition. Having mastered ancient languages, Chandra read the book and finally resolved the confusion of many years.
The reason forbidden spells are so powerful is that they borrow the divine power of the Fire God, Alix. This book records $M$ words that were taboo to Alix during his lifetime, such as the names of his rivals, hated plants, etc. When using a forbidden spell, if the incantation contains any taboo words, it will anger the divine power and fail, and the caster will also be punished.
For example, if "banana" is the only taboo word, and "an", "ban", and "analysis" are basic vocabulary words, and the required length of the forbidden spell is 11, then "bananalysis" is an invalid spell, while "analysisban" and "anbanbanban" are two valid spells. Note: A basic vocabulary word can appear zero, one, or multiple times in a forbidden spell; as long as the composition is different, they are considered different forbidden spells, even if the written form is the same.
With the puzzle solved, Chandra was in high spirits. She decided to calculate the total number of valid forbidden spells.
Since the answer may be very large, you only need to output the result modulo $1,000,000,007$.
Input
The first line contains three positive integers $N, M, L$.
The next $N$ lines each contain a string consisting only of lowercase English letters, representing a basic vocabulary word.
The next $M$ lines each contain a string consisting only of lowercase English letters, representing a taboo word.
Output
A single integer representing the answer (modulo $10^9+7$).
Examples
Input 1
4 2 10 boom oo ooh bang ob mo
Output 1
14
Note 1
There are 14 valid forbidden spells: boom/bang/oo, oo/oo/oo/oo/oo, oo/oo/ooh/ooh, oo/ooh/oo/ooh, oo/ooh/ooh/oo, ooh/oo/oo/ooh, ooh/oo/ooh/oo, ooh/ooh/boom, ooh/ooh/oo/oo, ooh/ooh/bang, ooh/bang/ooh, bang/oo/oo/oo, bang/ooh/ooh, bang/bang/oo.
Input 2
3 1 3 a ab aba aaa
Output 2
3
Note 2
There are 3 valid forbidden spells: a/a/ab, a/ab/a, a/aba. Note that a/ab/a and a/aba are counted as two different forbidden spells.
Input 3
3 1 14 ban an analysis banana
Output 3
15
Constraints
There are 10 test cases in total. The data scale and constraints for each test case are as follows:
| # | Constraints |
|---|---|
| #1 | $N = 5, M = 5, L \le 10$ |
| #2 | $N = 10, M = 1, L \le 50$ |
| #3 | $N = 20$ |
| #4 | $N = 20, M = 20, L \le 100$ |
| #5 | $N = 40, M = 10$ |
| #6 | $N = 50, M = 50$ |
| #7 | $N = 10, M = 2$, basic word length $\le 1$ |
| #8 | $N = 26, M = 10$ |
| #9 | $N = 20, M = 10$, basic word length $\le 2$ |
| #10 | $N = 50, M = 20$ |
For 100% of the data, $1 \le N, M \le 50$, $1 \le L \le 10^8$. The sum of the lengths of the basic vocabulary words does not exceed 100, and the sum of the lengths of the taboo words does not exceed 100. It is guaranteed that basic vocabulary words are not repeated and taboo words are not repeated.