#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> using namespace std; #define MOD 1000000007 #define N_MAX 2000002 typedef long long ll; typedef pair<ll, ll> P; ll inv[N_MAX],fac[N_MAX],finv[N_MAX]; void init(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<N_MAX;i++){ inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; fac[i]=fac[i-1]*(ll) i%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } } ll inv_(ll n){ if(n == 1) return 1; else return MOD-inv_(MOD%n)*(MOD/n)%MOD; } ll comb(ll n, ll r){ ll ans; if(n < r){ ans = 0; }else{ ans = (fac[n]*finv[r])%MOD; ans = (ans*finv[n-r])%MOD; ans = (ans+MOD)%MOD; } return ans; } int main(){ init(); ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int d, l, r, k; cin >> d >> l >> r >> k; int dl, dr; for(int i = 0; i < 30; i++){ if(l&(1<<i)) dl = i; if(r&(1<<i)) dr = i; } if((dl+dr-k)%2 == 1){ cout << 0 << endl; return 0; } int lca = (dl+dr-k)/2; if(lca < 0){ cout << 0 << endl; return 0; } ll ans = 1; for(int i = 0; i < d; i++){ ans *= fac[1<<i]; ans %= MOD; } if(dl == dr){ ans *= finv[1<<dl]; ans %= MOD; ans *= (ll)(1<<dl); ans %= MOD; ans *= (ll)(1<<(dl-lca-1)); ans %= MOD; ans *= fac[(1<<dl)-2]; ans %= MOD; }else{ if(dl != lca) ans *= inv[1<<(lca+1)]; } ans %= MOD; //cout << dl << ' ' << dr << ' ' << lca << endl; cout << ans << endl; }