const int N=1010, p=1e9+7;
int n, c[N][N]; map<LL, int> f[60];
LL l, r, z;
int F(int now, LL sum){
  if(now<0)return 1;
  if((1ll<<(LL)(now+1))-1ll<=sum/n)sum=((1ll<<(LL)(now+1))-1ll)*n;
  auto it=f[now].find(sum);
  if(it==f[now].end()){
    int res=0;
    for(int i=(z>>now)&1ll; i<=n&&(1ll<<now)*(LL)i<=sum; i+=2){
      res=(res+(LL)c[n][i]*F(now-1, sum-(LL)i*(1ll<<now))%p)%p;
    }
    f[now].insert(mkp(sum, res));
    return res;
  }
  return it->y;
}
signed main(){
  scanf("%d %lld %lld %lld", &n, &l, &r, &z);
  c[0][0]=1;
  for(int i=1; i<=n; i++){
    c[i][0]=1;
    for(int j=1; j<=i; j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
  }
  int res=(F(59, r)-F(59, l-1)+p)%p;
  printf("%d\n", res);
  return 0;
}

如果将 map 替换为 unordered_map 会在第 $49$ 到 $50$ 个点 TLE，有无懂哥讲讲是为什么