Description

Xiao C is very good at knapsack problems. He has a strange knapsack with a parameter $P$. After he puts some items into this knapsack, the knapsack’s weight is the total volume of the items modulo $P$.

Now there are $n$ types of items with different volumes. The $i$-th type has volume $V_i$, and each type has an unlimited supply. He will make $q$ queries. For each query, a weight $w_i$ is given. You need to answer how many ways there are to put items so that the weight of an initially empty knapsack becomes $w_i$. Note that two ways are considered different if and only if the types of items used are different, regardless of how many of each type are used. It is not hard to see that the total number of ways is $2^n$.

Since the answer may be large, you only need to output it modulo $10^9 + 7$.

Input Format

The first line contains three integers $n, q, P$, as described above.

The next line contains $n$ integers denoting $V_i$.

The next line contains $q$ integers denoting $w_i$.

Output Format

Output $q$ lines, each containing one integer, the answer for that query.

3 3 6
1 3 4
5 2 3

5
6
6

Hint

HAOI2018 round1 T1

Translated by ChatGPT 5