Welcome to Osim's maze!
Unfortunately, you are in the maze right now and you want to come outside the maze. But, in order to do that, you have to unlock some locks with keys. So, you are given $Q$ locks each of which is some integer $x_i$. You have an array of $N$ integers: $a_1, a_2, a_3, \dots, a_n$. A key for a lock $x_i$ is some non-empty subset of any positive size $k$ containing $s_1, s_2, \dots, s_k$ of the array such that $x_i \mathbin{\&} (s_1 \mathbin{|} s_2 \mathbin{|} ... \mathbin{|} s_k) == 0$ , where $\mathbin{\&}$ means $bitwise\hspace{1mm}AND$ and $\mathbin{|}$ means $bitwise\hspace{1mm}OR$. But, as you are a problem solver, you wonder how many subsets of your array exist as keys for a lock $x_i$.
Since the answer can be too large, you have to find the number $modulo$ $1000000007$.
Input
Input starts with an integer $T$, denoting the number of test cases.
Each case contains two integers $N$ and $Q$, denoting the number of elements of the array and the number of locks.
The next line contains $N$ integers $a_1, a_2, \dots, a_n$.
Each of the following $Q$ lines contains an integer $x_i$, denoting a lock of the maze.
Constraints
$1 ≤ T ≤ 5$$1 ≤ N ≤ 10^5$$1 ≤ Q ≤ 10^5$$1 ≤ a_i ≤ 10^6$$1 ≤ x_i ≤ 10^6$
Subtask 1 (10 points)
$1 ≤ T ≤ 5$$1 ≤ N ≤ 15$$1 ≤ Q ≤ 10^5$$1 ≤ a_i ≤ 10^6$$1 ≤ x_i ≤ 10^6$
Subtask 2 (30 points)
$1 ≤ T ≤ 5$$1 ≤ N ≤ 10^4$$1 ≤ Q ≤ 10^5$$1 ≤ a_i ≤ 10^3$$1 ≤ x_i ≤ 10^3$
Subtask 3 (60 points)
Original constraints
Output
For each test case, print "Case T:" (without quote) in the first line, where $T$ is the case number. Each of the next $Q$ lines should contain a single integer $y_i$, denoting the number of valid keys exist in the array $modulo$ $1000000007$ for the lock $x_i$.
Sample
| Input | Output |
|---|---|
2 4 1 1 2 3 4 4 4 2 2 2 3 5 5 2 | Case 1: 7 Case 2: 3 1 |
