H. Klein Moretti's Riddle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To prove your worth and earn your place in the Tarot Club, you must solve Klein's Riddle. You are given an array $$$a$$$ of size $$$n$$$ and an integer $$$k$$$. Additionally, you must answer $$$q$$$ queries. For each query, an integer $$$x_i$$$ is provided, and you need to determine how many ways there are to select a subsequence of $$$a$$$ with exactly $$$k$$$ elements such that the bitwise OR of its elements equals $$$x_i$$$. If no such subsequence exists, the answer should be $$$0$$$. Since the result can be very large, output it modulo $$$10^9 + 7$$$.

Input

The first line contains two integer $$$n$$$ and $$$k$$$ ($$$1\le k \le n \le 10^6$$$) — the size of the array $$$a$$$ and the number of elements to select, respectively.

The second line contains $$$n$$$ integers $$$a_1$$$,$$$a_2$$$,…,$$$a_n$$$ ($$$1\le a_i\le 10^6$$$) — the elements of array $$$a$$$.

The third line contains a single integer $$$q$$$ ($$$1\le q \le 10^6$$$) — the number of queries.

Next, there are $$$q$$$ lines, where the $$$i$$$-th line describes the $$$i$$$-th query. Each query contains a single integer $$$x_i$$$ ($$$ 1 \le x_i \le 10^6$$$).

Output

Print $$$q$$$ integers — the answers to the queries modulo $$$10^9+7$$$.

Example
Input
9 4
8 8 1 2 2 4 16 16 16
8
30
28
1300
31
15
16
29
35
Output
12
9
0
0
4
0
6
0