感觉写的没那么丑啊······

#include <bits/stdc++.h>
long long l, r, z;
int n;
const int mod = 1e9 + 7;
inline int add(int x, int y){
	return (x + y >= mod) ? x + y - mod : x + y;
}
inline int mul(int x, int y){
	return (int)(1ll * x * y % (1ll * mod));
}
inline int minus(int x, int y){
	return x < y ? x - y + mod : x - y;
}
int C[1005][1005];
int dp[62][2048][2];
int solve(long long b){
	memset(dp, 0, sizeof dp);
	dp[0][0][0] = 1;
	for(long long w = 0; w <= 60; ++w){
		for(int j = 0; j < (1 << 11); ++j){
			int st = (z & (1ll << w)) == 0ll ? 0 : 1;
			for(int k = st; k <= n; k += 2){
				int p = (j + k) % 2, q = (j + k) / 2;
				int g = mul(dp[w][j][1], C[n][k]);
				int h = mul(dp[w][j][0], C[n][k]);
				if(p && (b & (1ll << w))){
					dp[w + 1][q][1] = add(dp[w + 1][q][1], g);
					dp[w + 1][q][0] = add(dp[w + 1][q][0], h);
				}
				else if(p && !(b & (1ll << w))){
					dp[w + 1][q][1] = add(dp[w + 1][q][1], g);
					dp[w + 1][q][1] = add(dp[w + 1][q][1], h);
				}
				else if(!p && (b & (1ll << w))){
					dp[w + 1][q][0] = add(dp[w + 1][q][0], g);
					dp[w + 1][q][0] = add(dp[w + 1][q][0], h);
				}
				else {
					dp[w + 1][q][1] = add(dp[w + 1][q][1], g);
					dp[w + 1][q][0] = add(dp[w + 1][q][0], h);
				}
			}
		}
	}
	return dp[61][0][0];
}
signed main(){
	scanf("%d%lld%lld%lld", &n, &l, &r, &z);
	for(int i = 0; i <= 1000; ++i) C[i][0] = 1;
	for(int i = 1; i <= 1000; ++i){
		for(int j = 1; j <= 1000; ++j){
			C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
		}
	}
	printf("%d\n", minus(solve(r), solve(l - 1)));
	return 0;
}