#include #define rep(i,n) for(int i=0;i ; const int INF = 1e9; const int MOD = 1000000007; ll fac[3000000]; void init(){ fac[0] = 1; fac[1] = 1; for(int i=2;i<3000000;i++){ fac[i] = (fac[i-1] * i)%MOD; } } int depth(int p){ int i = 0; int res = 1; while(res <= p){ res *= 2; i ++; } return i; } ll power(int n,int k){ ll res = 1; for(int i=0;i> d >> l >> r >> k; int ld = depth(l); int rd = depth(r); //cout << ld << " "<< rd << endl; if((k-(rd-ld))%2 == 0 && ld - (k-(rd-ld))/2 >= 1 && rd-ld <= k){ int lca_d = ld - (k-(rd-ld))/2 ; //cout << lca_d << endl; ll ans; if(lca_d == ld) ans = (power(2,ld-1) * (power(2,rd-ld)))%MOD; else ans = (((power(2,lca_d-1) * power(2,ld-lca_d-1))%MOD * power(2,rd-lca_d-1))%MOD * 2)%MOD; //cout << lca_d-1 << " " << ld-lca_d-1 << " " << rd-lca_d-1 << endl; //cout << ans << endl; ll res = 2; for(ll i=2;i<=d;i++){ if(i==ld && i==rd) ans = (ans * fac[res-2])%MOD; else if(i==ld || i==rd) ans = (ans * fac[res-1])%MOD; else ans = (ans * fac[res])%MOD; res *= 2; } cout << ans << endl; }else{ cout << 0 << endl; return 0; } return 0; }