// // Created by yamunaku on 2019/10/25. // #include using namespace std; #define rep(i, n) for(int i = 0; i < (n); i++) #define repl(i, l, r) for(int i = (l); i < (r); i++) #define per(i, n) for(int i = ((n)-1); i >= 0; i--) #define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--) #define all(x) (x).begin(),(x).end() #define MOD 1000000007 #define IINF 1000000000 #define LINF 1000000000000000000 #define SP <<" "<< #define CYES cout<<"Yes"< vi; typedef vector> mti; typedef vector vl; typedef vector> mtl; vector fact; void buildFact(int n){ fact = vector(n + 1, 1); for(int i = 1; i <= n; i++){ fact[i] = fact[i - 1] * i % MOD; } } ll modpow(ll x, ll a){ ll ans = 1; while(a){ if(a & 1) ans = ans * x % MOD; a >>= 1; x = x * x % MOD; } return ans; } ll inv(ll x){ return modpow(x, MOD - 2); } int main(){ ll d, l, r, k; cin >> d >> l >> r >> k; buildFact(1 << d); int p = -1, q = -1; while(l) l /= 2, p++; while(r) r /= 2, q++; k -= (q - p); if(k % 2){ cout << 0 << endl; return 0; } k /= 2; if(p - k < 0){ cout << 0 << endl; return 0; } ll ans = 1; if(p == q){ if(k <= 0){ cout << 0 << endl; return 0; } rep(i, d){ if(i == p){ ans = ans * (1 << p) % MOD * (1 << (k - 1)) % MOD; ans = ans * fact[(1 << i) - 2] % MOD; }else{ ans = ans * fact[1 << i] % MOD; } } }else{ if(k < 0){ cout << 0 << endl; return 0; } rep(i, d){ if(i == q){ if(k == 0){ ans = ans * (1 << (q - p)) % MOD; }else{ ans = ans * (1 << (k - 1 + q - p)) % MOD; } ans = ans * fact[(1 << i) - 1] % MOD; }else{ ans = ans * fact[1 << i] % MOD; } } } cout << ans << endl; return 0; }