#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define REP1(i, n) for(int i=1; i<=(n); i++) #define RREP1(i, n) for(int i=(n); i>=1; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define out(...) printf(__VA_ARGS__) int dxy[] = {0, 1, 0, -1, 0}; void solve(); signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; } /*================================*/ #if DEBUG #define SIZE 100 #else #define SIZE 123450 #endif const int MAX = 1234560; const int MOD = 1e9+7; long long fac[MAX], finv[MAX], inv[MAX]; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; if (!fac[n]) COMinit(); return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int P(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; if (!fac[n]) COMinit(); return (fac[n] * finv[n-k]) % MOD; } int d,r,l,k; int ld=0,rd=0; int calc() { if (k>ld+rd) return 0; if ((ld+rd)%2 != k%2) return 0; int ans = 0; if (ld == rd) { /* k=2 → 2^ld * 2^0 k=4 → 2^ld * 2^1 */ ans = (1LL< rd) swap(ld, rd); if (rd-ld>k) return 0; int re = k - (rd-ld); if (re < 0 || re%2) return 0; int lcad = ld - re/2; ans = (1LL<>d>>l>>r>>k; COMinit(); REP(i,22) { int mi = 1LL<