Innocence

David는 어린 아이다. 그는 Nim 같은 조합 게임을 즐겨 한다. 그는 아마추어이지만 게임 이론에 조예가 깊다. 이번에는 그가 여러분을 위해 문제를 준비했다.

정수 $N$, $L$, $R$, $K$가 주어진다. 길이가 $N$이고, 모든 원소가 $L$ 이상 $R$ 이하이며, 원소들의 비트 XOR이 $K$와 같은 정수 배열의 개수를 구하라. 답은 $10^9 + 7$로 나눈 나머지로 출력한다.

David는 해답이 완전히 맞는지 확인하려고 여러 개의 $K$에 대한 답도 알고 싶어 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 다음과 같다. 첫 줄에 정수 $N$, $L$, $R$, $Q$가 공백으로 구분되어 주어진다. 이는 $N$, $L$, $R$은 같고 $K$만 다른 질의가 $Q$개 있다는 뜻이다. 둘째 줄에 질의할 정수 $K$ $Q$개가 공백으로 구분되어 주어진다.

$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}$.

$1 \le N \le 15$이고 $0 \le L, R, K < 2^{15}$을 만족하지 않는 테스트 케이스는 100개를 넘지 않는다.

각 질의에 대해 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제에서는 3을 하나, 4를 하나 고르는 방법이 두 가지 있으며, 이들의 XOR 값은 7이다.

두 번째 예제에서는 3을 하나, 4를 두 개 고르는 방법이 세 가지이고, 3을 세 개 고르는 방법이 한 가지이다. 이때 XOR 값은 3이다.