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$, count the number of arrays of length $N$ whose elements all lie between $L$ and $R$ (inclusive) and whose bitwise exclusive-OR equals $K$. Print the count modulo $10^9 + 7$.

David also wants you to answer several values of $K$ to make sure your solution is completely correct.

The first line contains one integer $T$, the number of test cases.

Each test case is described as follows. The first line contains four space-separated integers $N$, $L$, $R$ and $Q$, meaning there are $Q$ queries with the same $N$, $L$, $R$ but different $K$. The second line contains $Q$ space-separated integers $K$.

$1 \le T \le 1000$, $1 \le N \le 10^9$, $0 \le L \le R < 2^{30}$, $1 \le Q \le 100$, $0 \le K < 2^{30}$.

No more than 100 test cases fail to satisfy $1 \le N \le 15$ and $0 \le L, R, K < 2^{15}$.

For each query, print the answer modulo $10^9 + 7$ on its own line.

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.