#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second
#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=1e9+7;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=105;
const int D=61;
int dp[N][2][2][2],n,L,R,K;

void solve(){
	K=read();
	// cout<<"solve "<<n<<" "<<L<<" "<<R<<" "<<K<<endl;

	memset(dp,0,sizeof(dp));dp[D][0][0][0]=1;
	for(int i=D-1;i>=0;i--){
		int lc=((L>>i)&1),rc=((R>>i)&1),kc=((K>>i)&1);
		for(int x=0;x<=1;x++)for(int y=0;y<=1;y++)for(int z=0;z<=1;z++){
			add(dp[i][x][y][z],dp[i+1][x][y][z]);
			add(dp[i][x^lc][y^rc][z^kc],dp[i+1][x][y][z]);
		}
		// for(int x=0;x<=1;x++)for(int y=0;y<=1;y++)for(int z=0;z<=1;z++){
		// 	if(dp[i][x][y][z])cout<<"dp "<<i<<" "<<x<<" "<<y<<" "<<z<<" = "<<dp[i][x][y][z]<<endl;
		// }
	}

	int ls=0,rs=0,ks=0,ans=0;
	for(int i=0;i<D;i++){
		for(int x=0;x<=1;x++)for(int y=0;y<=1;y++)for(int z=0;z<=1;z++){
			int cnt=dp[i+1][x][y][z];if(cnt==0)continue;
			int vl=((((L>>i)&1)^x)==0)?ls:cmod(mod-ls);
			int vr=((((R>>i)&1)^y)==0)?rs:cmod(mod-rs);
			if((L>>i)&1)add(vl,(x==0?ksm(2,i):mod-ksm(2,i)));
			if((R>>i)&1)add(vr,(y==0?ksm(2,i):mod-ksm(2,i)));
			int val=cmod(vr+mod-vl);
			// cout<<"calc "<<i<<" "<<x<<" "<<y<<" "<<z<<" cnt = "<<cnt<<endl;
			// cout<<"vl,vr = "<<vl<<" "<<vr<<endl;
			// cout<<"val = "<<val<<endl;
			val=ksm(val,n);
			if((z^((K>>i)&1))==0)add(ans,1ll*val*cnt%mod);
			else add(ans,mod-1ll*val*cnt%mod);
			// cout<<"now ans = "<<ans<<endl;
		}
		if((L>>i)&1)add(ls,ksm(2,i));
		if((R>>i)&1)add(rs,ksm(2,i));
	}
	int val=(R-L)%mod;val=ksm(val,n);add(ans,val);

	cout<<1ll*ans*inv(ksm(2,D))%mod<<endl;
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	int tt=read();while(tt--){
		n=read(),L=read(),R=read()+1;int Q=read();
		for(int i=1;i<=Q;i++)solve();
	}

	return 0;
}