405810: GYM102114 I 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⁹ + 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 ≤ T ≤ 1000, 1 ≤ N ≤ 10⁹, 0 ≤ L ≤ R < 2³⁰, 1 ≤ Q ≤ 100, 0 ≤ K < 2³⁰.

It is guaranteed that no more than 100 test cases do not satisfy 1 ≤ N ≤ 15, 0 ≤ L, R, K < 2¹⁵.

For each query, print the answer modulo (10⁹ + 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.