Strange Backpack

Little C is very good at knapsack problems. He owns a strange backpack with a parameter \(P\). When he puts some items into the backpack, its weight is defined as the sum of the volumes of the items modulo \(P\).

Little C has \(n\) kinds of items, each of a different volume. The \(i\)-th item has a volume of \(V_i\), and there are infinitely many copies of each type. He will perform \(q\) queries. In each query, he gives a target weight \(w_i\), and you are to determine how many ways there are to select some items (the backpack is initially empty) such that the backpack's weight becomes \(w_i\). Two ways are considered different if and only if the set of item types chosen is different (the number of copies of each item does not matter). It is not hard to see that the total number of ways is \(2^n\) (each item type is either picked or not picked).

Since the answer may be very large, output it modulo \(10^9+7\).

Note: Each item type can only be taken or not taken, regardless of how many copies there are available.

inputFormat

The first line contains three integers \(n\), \(P\), and \(q\) -- the number of item types, the modulo parameter, and the number of queries, respectively.

The second line contains \(n\) integers \(V_1, V_2, \ldots, V_n\) representing the volume of each item.

The following \(q\) lines each contain one integer \(w_i\), the target weight for the query.

outputFormat

For each query, output a single integer representing the number of ways to achieve a backpack weight of \(w_i\), modulo \(10^9+7\).

sample

3 5 3
1 2 3
0
1
4

2
2
1