Counting Valid Cursed Spells

Chandra, a prodigy of fire magic, discovered that not all self‐created forbidden spells work as expected. In fire magic, a forbidden spell is constructed by concatenating a sequence of basic words from a set of N words to form a language string of length L (in characters). However, ancient lore reveals that there are M taboo words which the fire god Alexius abhors. If any forbidden word appears as a substring in the spell, the spell not only fails but also drains the caster's energy.

You are given the list of N basic words and M forbidden words. A spell is a sequence of basic words (each word may appear any number of times, including zero) whose total concatenated length is exactly L. Two spells are considered different if the sequence of basic words chosen is different, even if their concatenated string is the same.

Calculate the number of valid spells modulo $10^9+7$.

Input constraints:

• The first line contains three integers: N, M, and L.
• The second line contains N basic words separated by spaces.
• If M > 0, the third line contains M forbidden words separated by spaces. If M = 0, this line is empty.

Note: Forbidden words appearing as substrings anywhere in the concatenated spell render it invalid.

inputFormat

The input consists of:

1. A line with three integers N, M and L.
2. A line with N basic words separated by spaces.
3. If M > 0, a line with M forbidden words separated by spaces; otherwise, this line is empty.

outputFormat

Output a single integer: the number of valid spells modulo $10^9+7$.

sample

2 1 3
a b
ab

4