See Problem N for PDF statements.

Yukikaze is learning stringology. She found a series of interesting problems at the end of her textbook as follows.

We consider a string to be good if it satisfies the following conditions:

•  It consists of decimal digits less than .
•  Digit appears at least times.

We consider two strings to be different if they are different in length or there exists an integer such that the letters in their -th position are different.
The problem in the textbook asks for the number of different good strings of length .

输入描述:

The first line contains a single integer  (), indicating that a good string consists of decimal digits less than .

The second line contains  integers  (, ), indicating that the decimal digit  appears at least  times in a good string.

The third line contains a single integer  (), indicating the number of queries.

Each of the next  lines contains a single integer  (), indicating the length of the string.

输出描述:

For each query, output an integer in a single line indicating the number of different good strings of length . As the answer may be large, please output the answer modulo .

2
1 1
3
3
5
7

6
30
126

If we set , , , then the answer is , including .

6
11 45 14 11 45 14
3
114514
1919
810

519265932
6372511
784491879