Problem D
Highway to Mount Fansipan

In the year $3\, 030$, Highway to mount Fansipan is the most popular TV game show in Vietnam.

In this game show, four contestants are given a crossword puzzle. The crossword consists of $n$ horizontal words. The first letters of the $n$ words form a hidden message when read from top to bottom. The first contestant who finds the hidden message wins the game.

In the above figure, the crossword has $4$ horizontal words: invite, cat, party and cow. The first letters of these $4$ words form the hidden message icpc.

This year, you are tasked with creating a crossword for Highway to mount Fansipan. You are given the following requirements:

• There must be $n$ horizontal words. The $i$-th word must have exactly $w_ i$ characters.

• You are given a dictionary with $d$ words. Each horizontal word and the hidden message must be in the given dictionary.

• The $n$ horizontal words and the hidden message must be pairwise different.

As an expert programmer, generating a crossword satisfying the above requirements is an easy task for you. But you are wondering how many different ways of generating crossword there are. Two crosswords are considered different if at least one of the $n$ horizontal words are different.

Input

The first line of the input contains a single integer $T$ — the number of test cases. $T$ test cases follow, each test case is presented as below:

• The first line contains a positive integer $n$ — the number of horizontal words. The sum of $n$ in all test cases does not exceed $10^5$.

• The second line contains exactly $n$ positive integers, $w_1, w_2, \ldots , w_ n$ $(1 \le w_ i \le 50)$, where $w_ i$ is the length of the $i$-th horizontal word.

• The third line contains a positive integer $d$. The sum of $d$ in all test cases does not exceed $10^5$.

• In the next $d$ lines, each line contains a single word in the dictionary. Each word contains between $1$ and $50$ lowercase English letters. No two words are equal. The total length of all words in all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output a single integer — the number of different ways to generate the crossword, modulo $10^9 + 7$.

2
4
6 3 5 3
5
invite
icpc
party
cat
cow
4
6 3 5 3
4
invite
party
cat
cow

2
0