Dereck is a linguist tasked on computing the amount of words of a certain length in a new language called "Aionian". A word is considered valid if the sequence of characters does not include the same letter twice in a row or two vowels in a row.
Given the vowels and consonants of the language, calculate the number of words of given lengths.
Input Specification
The first line contains the number of vowels, , with the next lines being the vowels.
The next line contains the number of consonants, with the next lines being the consonants.
The next line contains the number of queries, , in which the next lines are the lengths Dereck wants you to calculate.
Output Specification
Output the number of words with the length specified, modulo .
Sample Input
2
A
E
3
B
C
D
3
10
3
7
Sample Output
564000
66
11640
Comments