Xiao C is very good at knapsack problems. He has a strange backpack with a parameter $P$. When he puts several items into this backpack, the weight of the backpack is the sum of the volumes of the items modulo $P$.

Now, Xiao C has $n$ items with different volumes, where the $i$-th item has a volume of $V_i$. There are an infinite number of each item. He will perform $q$ queries. For each query, he gives a weight $w_i$, and you need to answer how many ways there are to put items into an initially empty backpack such that the resulting weight is $w_i$. Note that two ways are considered different if and only if the set of types of items included is different, regardless of the number of each item included. It is not difficult to see that the total number of ways is $2^n$.

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

Input

The first line contains three integers $n, q, P$. The next line contains $n$ integers representing $V_i$. The next line contains $q$ integers representing $w_i$.

Output

Output $q$ lines, each containing one integer representing the answer.

Examples

Input 1

3 3 6
1 3 4
5 2 3

Output 1

5 6 6

Note 1

For the first query $5$, the choices $\{1\}, \{1, 3\}, \{1, 4\}, \{3, 4\}, \{1, 3, 4\}$ are all valid schemes.

Input 2

See knapsack/knapsack2.in in the contestant directory.

Output 2

See knapsack/knapsack2.ans in the contestant directory.

Constraints

For all data, $1 \le n, q \le 10^6$, $3 \le P \le 10^9$, $0 < V_i, w_i < P$. It is guaranteed that all $V_i$ are distinct.