Emma is really fond of integers and loves playing with them. Her friends were jealous, and to test her, one of them gave her a problem.
Emma is given a list of integers and is asked a set of queries. Each query is denoted by an integer , for which you have to return the sum of product of all possible sublists having exactly elements.
Emma has got stuck in this problem and you being her best friend have decided to help her write a code to solve it. Since the answers can be very large, print the answers modulo .

Input Format
First line has an integer , denoting the number of integers in list . Next line contains space separated integers. The third line contains integer , and next lines have a single integer .

Output Format
For each of the queries, print the corresponding answer in a new line.

NOTE Sublist here refers to selecting elements from a list of elements. There will be ways to do that, it doesn't matter if two elements are same.

Constraints

Sample Input #00

3
1 2 3
2
1
2

Sample Output #00

6
11

Sample Input #01

3
1 2 2
1
2

Sample Output #01

8

Explanation

Sample #00:
For possible sublists are so answer is .
For possible sublists are so answer is .

Sample #01:
For possible sublists are so answer is .