P3715 [BJOI2017] Magic Incantations

Chandra is a prodigy of magic. Since receiving the baptism of the Church of Fire at the age of one, Chandra has shown unparalleled affinity for the fire element and easily mastered various obscure spells. This also owes to Chandra’s extraordinary talent for languages, which lets her fluently pronounce the very awkward magical words in incantations. She did not encounter obstacles until the age of fourteen, when she began studying powerful forbidden spells. According to the rules of fire magic, a forbidden spell is composed of $N$ basic words. During casting, as long as she concentrates and speaks an utterance of length exactly $L$ formed by these words, she can unleash a fire spell of unimaginable power. Magicians in the past summarized several of the most fluent composition methods to help the caster complete the spell at the fastest speaking speed. However, Chandra, a genius in both magic and language, was not satisfied with those handed‑down forbidden spells, because she could effortlessly speak forbidden utterances that ordinary people could hardly pronounce. Yet in actual casting, Chandra found that some of her self‑created forbidden spells not only failed to produce the expected effect after being chanted, but also rapidly drained her mental strength, causing great discomfort. This problem puzzled Chandra greatly. She read many classics, consulted magic scholars everywhere, and, despite the mental torment, tried new incantations again and again, hoping to find the answer. Many years later, during an expedition to ancient ruins, Chandra accidentally entered an unknown shrine of the fire god Ailikesi (pinyin). Based on the geomorphic features, the shrine should be tens of thousands of years old, which is extremely rare. Chandra carefully explored, followed the flow of magic, and came to a secret chamber. She saw a book floating at the center of the chamber. Protected by magic, the book was in perfect condition. Proficient in ancient languages, Chandra read it and finally solved her years‑long confusion. Forbidden spells are so powerful because the incantation borrows the divine power of the fire god Ailikesi. This book recorded $M$ taboo words that Ailikesi hated in life, such as the name of a rival in love, a disliked plant, and so on. When using a forbidden spell, if the utterance contains any taboo word, the divine power will be angered and the spell will fail, and the caster will suffer punishment as well. For example, if `banana` is the only taboo word, `an`, `ban`, `analysis` are the basic words, and the forbidden spell length must be $11$, then `bananalysis` is an invalid spell, while `analysisban` and `anbanbanban` are two valid spells. Note: a basic word can appear zero, one, or multiple times in a forbidden spell; as long as the composition (sequence of basic words) is different, they are considered different forbidden spells, even if the written string is the same. With the puzzle solved, Chandra was delighted. She decided to compute how many valid forbidden spells there are in total. Since the answer can be large, you only need to output the result modulo $10 ^ 9 + 7$.

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 word. The next $M$ lines each contain a string consisting only of lowercase English letters, representing a taboo word.

A single line containing one integer, the answer (mod $10^9+7$).

[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] The valid forbidden spells are `a/ab`, `ab/a`, and `aba`, three in total. Note that `ab/a` and `aba` count as two different forbidden spells. [Constraints and Agreements] This problem has $10$ test points. The following table shows the data scale and agreements for each test point:  For $100\%$ of the testdata, $1 \le N, M \le 50$, $1 \le L \le 10^8$, the sum of lengths of the basic words does not exceed $100$, and the sum of lengths of the taboo words does not exceed $100$. It is guaranteed that the basic words are distinct and the taboo words are distinct. Translated by ChatGPT 5