A text without spaces

memoization dynamic programming hash table counting text editors

Spaces and punctuation have been removed from a text. In how many ways can it be cut into dictionary words again? The answer can be huge, so print its remainder modulo 10⁹ + 7.

From the second test on, the dictionary is the 14,871 words of War and Peace (in the original Russian) that occur in the novel at least three times, plus the one-letter words а, в, и, к, о, с, у, я. The texts are sentences and paragraphs of the novel. «Наполеон» (Napoleon) reads in two ways: «наполеон» and «на поле он» (“he is on the field”).

Input

The first line holds m, the number of words in the dictionary, the second the words themselves separated by spaces (at most 24 letters each). Then q (1 ≤ q ≤ 30) and q lines, texts of up to 5000 letters. All words and texts consist of lowercase Russian letters.

Output

For each text, the number of ways modulo 10⁹ + 7.

Examples

Example 1

Input

4
а б аб ба
3
абаб
ба
в

Output

5
2
0

Limits

Time · Python: 5000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Let ways(i) be the number of ways to read the text from letter i to the end. How is it expressed through ways with larger indices? And how many times will a recursion compute the same ways(i)?

2The idea

ways(i) is the sum of ways(j) over all j for which the piece of text from i to j − 1 is a dictionary word; ways(n) = 1. A recursion straight from this formula is correct, but it arrives at the same position by different roads, as many times as there are ways to read the beginning. If the answer for each position is remembered, each is computed once.

3Walkthrough

With memory there are n + 1 positions, each with at most 24 checks of “is there such a word”: a hash table answers in O(1) on average. It is convenient to fill the table of ways from the end, without recursion: on a text of 5000 letters recursion would go 5000 deep, while Python’s default limit is a thousand calls.

Without memory the paragraph about Natasha from the article would take 3.4·10¹¹ calls. With memory, 133 positions.

Take the remainder at every step: otherwise the numbers overflow in Go, and in Python they become huge and slow.

3+Solution

4Complexity

O(n·L) checks for a text of length n, where L = 24 is the length of the longest word; plus the time to hash the pieces.

5Common mistakes

Recursion without memory. Correct, but exponential: on the paragraphs of the fourth test it will never finish.
Deep recursion with memory. The sixth test has 5000 nested calls: in Python without sys.setrecursionlimit that is a RecursionError. A table filled from the end does without recursion.
The remainder only at the end. The numbers grow exponentially with the length of the text; the remainder has to be taken at every addition.

Algorithms behind it

TEC Technique Memoization Remember a function’s answer for each set of arguments so as not to compute it again: an exponential turns into a polynomial. O(the number of distinct arguments × the work per call) 2 problems DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems