#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using namespace std;
using i64 = long long;
using i128 = __int128_t;
using pii = pair<int, int>;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

const int P = 1e9 + 7;
void add(int &x, int y) { (x += y) >= P && (x -= P); }
int Add(int x, int y) { return (x += y) >= P ? (x - P) : x; }
void sub(int &x, int y) { (x -= y) < 0 && (x += P); }
int Sub(int x, int y) { return (x -= y) < 0 ? (x + P) : x; }
void mul(int &x, int y) { x = 1ll * x * y % P; }
int Mul(int x, int y) { return 1ll * x * y % P; }
int power(int a, int b, int c = 1) {
    for (; b; b >>= 1, mul(a, a))
        if (b & 1) mul(c, a);
    return c;
}

int p, ways[33][2][2], dp[33][2][2][2];
int get(int x, int lb, bool odd) {
    int res = 0;
    per(i, p, 0) {
        if (x >> i & 1) {
            if (lb < i) continue;
            bool tmp = odd;
            if (lb == i) tmp ^= (x >> i & 1);
            (tmp ? sub : add)(res, 1 << i);
        }
    }
    return res;
}

void solve() {
    int n, l, r, q;
    cin >> n >> l >> r >> q;

    if (r == 0) {
        while (q--) {
            int k;
            cin >> k;
            cout << (k == 0) << "\n";
        }
        return;
    }

    p = 32 - __builtin_clz(r++);
    rep(i, 0, p - 1) {
        rep(x, 0, 1) rep(y, 0, 1) {
            ways[i][x][y] = power(Sub(get(r, i, y), get(l, i, x)), n);
        }
    }
    int offset = power(r - l, n), coef = power(1 << p, P - 2);

    while (q--) {
        int k; 
        cin >> k;
        // rep(s, 1, (1 << p) - 1) {
        //     int sum = 0;
        //     rep(i, l, r - 1) (__builtin_parity(i & s) ? sub : add)(sum, 1);
        //     sum = power(sum, n);
        //     (__builtin_parity(k & s) ? sub : add)(ans, sum);
        // }
        int hb = (k == 0) ? 0 : (32 - __builtin_clz(k));
        if (hb > p) {
            cout << "0\n";
            continue;
        }
        int ans = offset;
        memset(dp[p], 0, sizeof dp[p]);
        dp[p][0][0][0] = 1;
        per(i, p, 1) {
            memcpy(dp[i - 1], dp[i], sizeof dp[i - 1]);
            bool pl = (l >> (i - 1) & 1);
            bool pr = (r >> (i - 1) & 1);
            bool pk = (k >> (i - 1) & 1);
            rep(x, 0, 1) rep(y, 0, 1) rep(z, 0, 1) {
                int val = dp[i][x][y][z];
                if (!val) continue;
                add(dp[i - 1][x ^ pl][y ^ pr][z ^ pk], val);
                int cur = Mul(val, ways[i - 1][x ^ pl][y ^ pr]);
                ((z ^ pk) ? sub : add)(ans, cur);
            }
        }
        mul(ans, coef);
        cout << ans << "\n";
    }
}

int main() {
    // freopen("1.in", "r", stdin);
	ios::sync_with_stdio(0), cin.tie(0);

    int T; cin >> T;
    while (T--) solve();

	return 0;
}