Girls Invitational '18 S3 - Unknown Words

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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, V (1 \le V \le 10^4), with the next V lines being the vowels.
The next line contains the number of consonants, C (1 \le C \le 10^4) with the next C lines being the consonants.
The next line contains the number of queries, L (1 \le L \le 10^4), in which the next L lines are the lengths Dereck wants you to calculate.

Output Specification

Output the number of words with the length specified, modulo 10^9+7.

Sample Input

2
A
E
3
B
C
D
3
10
3
7

Sample Output

564000
66
11640

Comments

There are no comments at the moment.