Innocence

David is a young child. He likes playing combinatorial games, for example, the Nim game. He is just an amateur but he is sophisticated with game theory. This time he has prepared a problem for you.
Given integers $N, L, R$ and $K$, you are asked to count in how many ways one can arrange an integer array of length $N$ such that all its elements are ranged from $L$ to $R$ (inclusive) and the bitwise exclusive-OR of them equals to $K$. To avoid calculations of huge integers, print the number of ways in modulo $(10^9 + 7)$.
In addition, David would like you to answer with several integers $K$ in order to ensure your solution is completely correct.

The first line contains one integer $T$, indicating the number of test cases.
The following lines describe all the test cases. For each test case:
The first line contains four space-separated integers $N, L, R$ and $Q$, indicating there are $Q$ queries with the same $N, L, R$ but different $K$.
The second line contains $Q$ space-separated integers, indicating several integers $K$.
$1 \leq T \leq 1000$, $1 \leq N \leq 10^9$, $0 \leq L \leq R < 2^{30}$, $1 \leq Q \leq 100$, $0 \leq K < 2^{30}$.
It is guaranteed that no more than $100$ test cases do not satisfy $1 \leq N \leq 15$, $0 \leq L, R, K < 2^{15}$.

For each query, print the answer modulo $(10^9 + 7)$ in one line.

3
2 3 4 2
0 7
3 3 4 2
3 4
5 5 7 4
5 6 7 8

2
2
4
4
61
61
61
0

In the first sample, there are two ways to select one number 3 and one number 4 such that the exclusive-OR of them is 7.
In the second sample, there are three ways to select one number 3 and two numbers 4 and one way to select three numbers 3 such that the exclusive-OR of them is 3.

2018 Multi-University Training Contest 5