시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

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 (109 + 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 ≤ 109, 0 ≤ L ≤ R < 230, 1 ≤ Q ≤ 100, 0 ≤ K < 230.

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

## 출력

For each query, print the answer modulo (109 + 7) in one line.

## 예제 입력 1

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


## 예제 출력 1

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.