#include using namespace std; int dig(int x){ int d = 0; while(x){ x /= 2; d++; } return d; } long long mod = 1000000007,f[1<<21]; void solve(){ f[0] = 1; int i; for(i=1;i<(1<<20);i++){ f[i] = i*f[i - 1]%mod; } } int main(){ int i,d,l,r,k; cin >> d >> l >> r >> k; int d1 = dig(l),d2 = dig(r); if(d1 + d2 - k<=0 || (d1 + d2 - k)&1){ cout << 0 << endl; return 0; } solve(); int dep = (d1 + d2 - k)/2; if(dep>d1 || dep>d2){ cout << 0 << endl; return 0; } long long ans = 1; for(i=1;i<=d;i++){ if(i!=d2){ (ans *= f[1<<(i - 1)]) %= mod; } } int d3 = d2 - dep; if(dep!=d1) d3--; if(d1==d2){ (ans *= (1<<(d2 - 1))) %= mod; (ans *= f[(1<<(d2 - 1)) - 2]) %= mod; (ans *= (1<<(d3))) %= mod; }else{ (ans *= f[(1<<(d2 - 1)) - 1]) %=mod; (ans *= (1<<(d3))) %= mod; } cout << ans << endl; }