Problem Description

Chandra is a magical prodigy.

Since her baptism in the Fire Church at the age of one, Chandra has shown an unparalleled affinity for fire elements, easily mastering various esoteric spells. This is largely due to Chandra's extraordinary linguistic talent, allowing her to fluently speak the extremely difficult magical terms in spells.

However, when she began learning powerful forbidden spells at the age of fourteen, Chandra encountered obstacles.

According to the rules of fire magic, forbidden spells are composed of $N$ basic terms. To cast a spell, one must concentrate their mental energy and recite a phrase composed of these terms with a length exactly equal to $L$, unleashing a fire spell of unimaginable power. Past magicians have summarized several most coherent combination methods to facilitate spellcasters in completing the spell at the fastest speed.

But Chandra, with her dual talents in magic and language, is not satisfied with these traditional forbidden spells, as she can effortlessly speak phrases that are almost impossible for ordinary people. However, in practice, Chandra found that some of her self-created spells not only failed to produce the expected effects but also rapidly drained her mental energy, causing great discomfort.

This problem puzzled Chandra greatly. She read extensively, visited magical scholars everywhere, and repeatedly tried new spells despite the mental torment, hoping to find the answer.

Many years passed, and during an exploration of an ancient ruin, Chandra accidentally entered an unnamed temple of the Fire God Alex. Based on the rock features, the temple should be over ten thousand years old, which is extremely rare. Chandra cautiously explored the temple, following the flow of magic to a secret chamber. She saw a book floating in the center of the chamber. Under magical protection, the book was in perfect condition. Chandra, who was proficient in ancient languages, read the book and finally solved the long-standing mystery.

The power of forbidden spells lies in the fact that the spells borrow the divine power of the Fire God Alex. This book records $M$ taboo terms from Alex's life, such as the names of enemies and disliked plants. When using forbidden spells, if the phrase contains any taboo terms, it will anger the divine power and become ineffective, and the spellcaster will also be punished.

For example, if banana is the only taboo term, and an, ban, analysis are basic terms, with a required spell length of $11$, then bananalysis is an invalid spell, while analysisban and anbanbanban are two valid spells. Note: A basic term can appear zero, one, or multiple times in a forbidden spell; as long as the composition method is different, it is considered a different forbidden spell, even if the written form is the same.

Having solved the puzzle, Chandra felt great relief. She decided to calculate how many valid forbidden spells there are.

Since the answer may be very large, you only need to output the result modulo $10^9 + 7$.

Input Format

The first line contains three positive integers $N, M, L$.

The next $N$ lines each contain a string consisting of lowercase English letters, representing a basic term.

The next $M$ lines each contain a string consisting of lowercase English letters, representing a taboo term.

Output Format

A single line containing an integer, representing the answer modulo $10^9 + 7$.

Sample Input and Output

Input Sample #1

4 2 10
boom
oo
ooh
bang
ob
mo

Output Sample #1

14

Input Sample #2

3 1 3
a
ab
aba
aaa

Output Sample #2

3

Input Sample #3

3 1 14
ban
an
analysis
banana

Output Sample #3

15

Notes/Hints

Sample Explanation 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.

Sample Explanation 2

There are three valid forbidden spells: a/ab, ab/a, and aba. Note that ab/a and aba are considered two different forbidden spells.

Data Scale and Agreements

There are 10 test cases in total.

The following table shows the data scale and agreements for each test case:

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 terms does not exceed 100, and the sum of the lengths of the taboo terms does not exceed 100. Basic terms and taboo terms are guaranteed to be unique.

见题面 Input 部分

见题面 Output 部分