#include #include #include using namespace std; using ll = long long; const ll MOD = (ll)1e9 + 7; int main() { int d, l, r, k, MAX_d = 20; cin >> d >> l >> r >> k; vector pow2(MAX_d + 1, 1), sum(MAX_d + 1, 0), fac((1<<(MAX_d + 1)) + 1,1); //2冪を前計算 for (int i = 2; i < MAX_d + 1; ++i) pow2[i] = pow2[i - 1] * 2; //2冪の和を前計算 for (int i = 1; i < MAX_d + 1; ++i) sum[i] = sum[i - 1] + pow2[i]; //階乗を前計算 for (ll i = 1; i < (1 << MAX_d) + 1; ++i) fac[i] = (fac[i] * i) % MOD; //l,rを深さに変換 l = lower_bound(sum.begin(), sum.end(), l) - sum.begin(); r = lower_bound(sum.begin(), sum.end(), r) - sum.begin(); int lca = -1; //lcaが存在するならそのlcaの深さを計算 if ((l + r - k) > 1 && (l + r - k) % 2 == 0) lca = (l + r - k) / 2; //lcaが条件を満たしていない場合コーナー if(lca == -1 || lca > l || lca > r){ cout << 0 << endl; return 0; } ll ans = 1; //上の段からl,r以外の頂点の順列の数え上げ for (int i = 1; i <= d; ++i) { ll cnt = pow2[i]; if (i == l) cnt--; if (i == r) cnt--; (ans *= fac[cnt]) %= MOD; } //lcaとなるような頂点の位置についての数え上げ (ans *= pow2[lca]) %= MOD; //lcaを決め打ちした時のlの位置についての数え上げ (ans *= pow2[l - lca]) %= MOD; //lcaを決め打ちした時のrの位置についての数え上げ (ans *= pow2[r - lca]) %= MOD; //lcaについて、子は左右について2通りのパターンがあるため (ans *= 2) %= MOD; cout << ans << endl; return 0; }