#include using namespace std; template vector operator-(vector a) { for (auto&& e : a) e = -e; return a; } template vector& operator+=(vector& l, const vector& r) { l.resize(max(l.size(), r.size())); for (int i = 0; i < (int)r.size(); ++i) l[i] += r[i]; return l; } template vector operator+(vector l, const vector& r) { return l += r; } template vector& operator-=(vector& l, const vector& r) { l.resize(max(l.size(), r.size())); for (int i = 0; i < (int)r.size(); ++i) l[i] -= r[i]; return l; } template vector operator-(vector l, const vector& r) { return l -= r; } template vector& operator<<=(vector& a, size_t n) { return a.insert(begin(a), n, 0), a; } template vector operator<<(vector a, size_t n) { return a <<= n; } template vector& operator>>=(vector& a, size_t n) { return a.erase(begin(a), begin(a) + min(a.size(), n)), a; } template vector operator>>(vector a, size_t n) { return a >>= n; } template vector operator*(const vector& l, const vector& r) { if (l.empty() or r.empty()) return {}; vector res(l.size() + r.size() - 1); for (int i = 0; i < (int)l.size(); ++i) for (int j = 0; j < (int)r.size(); ++j) res[i + j] += l[i] * r[j]; return res; } template vector& operator*=(vector& l, const vector& r) { return l = l * r; } template vector inverse(const vector& a) { assert(not a.empty() and not (a[0] == 0)); vector b{1 / a[0]}; while (b.size() < a.size()) { vector x(begin(a), begin(a) + min(a.size(), 2 * b.size())); x *= b * b; b.resize(2 * b.size()); for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = -x[i]; } return {begin(b), begin(b) + a.size()}; } template vector operator/(vector l, vector r) { if (l.size() < r.size()) return {}; reverse(begin(l), end(l)), reverse(begin(r), end(r)); int n = l.size() - r.size() + 1; l.resize(n), r.resize(n); l *= inverse(r); return {rend(l) - n, rend(l)}; } template vector& operator/=(vector& l, const vector& r) { return l = l / r; } template vector operator%(vector l, const vector& r) { if (l.size() < r.size()) return l; l -= l / r * r; return {begin(l), begin(l) + (r.size() - 1)}; } template vector& operator%=(vector& l, const vector& r) { return l = l % r; } template vector derivative(const vector& a) { vector res(max((int)a.size() - 1, 0)); for (int i = 0; i < (int)res.size(); ++i) res[i] = (i + 1) * a[i + 1]; return res; } template vector primitive(const vector& a) { vector res(a.size() + 1); for (int i = 1; i < (int)res.size(); ++i) res[i] = a[i - 1] / i; return res; } template vector logarithm(const vector& a) { assert(not a.empty() and a[0] == 1); auto res = primitive(derivative(a) * inverse(a)); return {begin(res), begin(res) + a.size()}; } template vector exponent(const vector& a) { assert(a.empty() or a[0] == 0); vector b{1}; while (b.size() < a.size()) { vector x(begin(a), begin(a) + min(a.size(), 2 * b.size())); x[0] += 1; b.resize(2 * b.size()); x -= logarithm(b); x *= {begin(b), begin(b) + b.size() / 2}; for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = x[i]; } return {begin(b), begin(b) + a.size()}; } namespace fft { struct C { double x, y; C(double _x = 0, double _y = 0) : x(_x), y(_y) {} }; C operator+(C l, C r) { return {l.x + r.x, l.y + r.y}; } C operator-(C l, C r) { return {l.x - r.x, l.y - r.y}; } C operator*(C l, C r) { return {l.x * r.x - l.y * r.y, l.x * r.y + l.y * r.x}; } C operator~(C a) { return {a.x, -a.y}; } vector w{1}; void ensure(int n) { for (int m = w.size(); m < n; m *= 2) { C dw{cos(acos(0) / m), sin(acos(0) / m)}; w.resize(2 * m); for (int i = 0; i < m; ++i) w[m + i] = w[i] * dw; } } void fft(vector& a, int n, bool inverse) { assert((n & (n - 1)) == 0); ensure(n); if (not inverse) { for (int m = n; m >>= 1; ) { for (int s = 0, k = 0; s < n; s += 2 * m, ++k) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { C x = a[i], y = a[j] * w[k]; a[i] = x + y, a[j] = x - y; } } } } else { for (int m = 1; m < n; m *= 2) { for (int s = 0, k = 0; s < n; s += 2 * m, ++k) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { C x = a[i], y = a[j]; a[i] = x + y, a[j] = (x - y) * ~w[k]; } } } double inv = 1.0 / n; for (auto&& e : a) e.x *= inv, e.y *= inv; } } void real_fft(vector& a) { if (a.size() < 2) return; assert(a.size() % 2 == 0); int n = a.size() / 2; for (int i = 0; i < n; ++i) a[i] = {a[2 * i].x, a[2 * i + 1].x}; fft(a, n, false); for (int s = n; s >>= 1; ) for (int i = s, j = 2 * s; j-- > s; ++i) { C wa((1 + w[i].y) / 2, -w[i].x / 2), wb((1 - w[i].y) / 2, w[i].x / 2); a[2 * i] = a[i] * wa + ~a[j] * wb, a[2 * j + 1] = ~a[2 * i]; } a[1] = a[0].x - a[0].y, a[0] = a[0].x + a[0].y; } void real_ifft(vector& a) { if (a.size() < 2) return; assert(a.size() % 2 == 0); int n = a.size() / 2; for (int i = 0; i < n; ++i) { C wa((1 + w[i].y) / 2, w[i].x / 2), wb((1 - w[i].y) / 2, -w[i].x / 2); a[i] = a[2 * i] * wa + a[2 * i + 1] * wb; } fft(a, n, true); for (int i = n; i--; ) a[2 * i].x = a[i].x, a[2 * i + 1].x = a[i].y; } } // namespace fft template > T power(T a, long long n, F op = multiplies(), T e = {1}) { assert(n >= 0); T res = e; while (n) { if (n & 1) res = op(res, a); if (n >>= 1) a = op(a, a); } return res; } template struct Modular { using M = Modular; unsigned v; Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {} M operator-() const { return M() -= *this; } M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; } M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; } M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; } M& operator/=(M r) { return *this *= power(r, Mod - 2); } friend M operator+(M l, M r) { return l += r; } friend M operator-(M l, M r) { return l -= r; } friend M operator*(M l, M r) { return l *= r; } friend M operator/(M l, M r) { return l /= r; } friend bool operator==(M l, M r) { return l.v == r.v; } }; template array, K> mint_fft(const vector>& a, int sz) { array, K> res; for (size_t p = 0; p < K; ++p) { res[p].resize(sz); for (int i = 0; i < (int)a.size(); ++i) res[p][i] = (a[i].v >> (p * B)) & ((1 << B) - 1); fft::real_fft(res[p]); } return res; } template vector> mint_ifft(array, N> a) { int n = a[0].size(); vector> res(n); for (size_t p = 0; p < N; ++p) { fft::real_ifft(a[p]); auto base = power(Modular(2), p * B); for (int i = 0; i < n; ++i) res[i] += round(a[p][i].x) * base; } return res; } template array, 2 * K - 1> operator*( const array, K>& l, const array, K>& r) { int n = l[0].size(); array, 2 * K - 1> res; for (size_t p = 0; p < K; ++p) for (size_t q = 0; q < K; ++q) { res[p + q].resize(n); for (int i = 0; i < n; ++i) res[p + q][i] = res[p + q][i] + l[p][i] * r[q][i]; } return res; } template vector> operator*( const vector>& l, const vector>& r) { if (l.empty() or r.empty()) return {}; int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1); if (min(n, m) < 30) { vector res(n + m - 1); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) res[i + j] += (l[i] * r[j]).v; return {begin(res), end(res)}; } bool eq = l == r; auto a = mint_fft(l, sz), b = eq ? a : mint_fft(r, sz); auto res = mint_ifft(a * b); return {begin(res), begin(res) + (n + m - 1)}; } constexpr long long mod = 1e9 + 7; using Mint = Modular; vector fact, inv_fact, minv; void prepare(int n) { fact.resize(n + 1), inv_fact.resize(n + 1), minv.resize(n + 1); for (int i = 0; i <= n; ++i) fact[i] = i ? i * fact[i - 1] : 1; inv_fact[n] = 1 / fact[n]; for (int i = n; i; --i) inv_fact[i - 1] = i * inv_fact[i]; for (int i = 1; i <= n; ++i) minv[i] = inv_fact[i] * fact[i - 1]; } Mint binom(int n, int k) { if (k < 0 or k > n) return 0; return fact[n] * inv_fact[k] * inv_fact[n - k]; } template<> Mint& Mint::operator/=(Mint r) { return *this *= r.v < minv.size() ? minv[r.v] : power(r, mod - 2); } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, M, D1, D2; cin >> N >> M >> D1 >> D2; int n = N - 1; int m = M - D1 * (N - 1); int d = D2 - D1 + 1; if (m <= 0) return cout << 0 << '\n', 0; // [X^(m-1)](1-X^d)^n/(1-X)^(n+2) prepare(n + 2); vector f(m), g(m); for (int i = 0; i <= n; ++i) { if (i * d >= m) break; f[i * d] = binom(n, i); if (i & 1) f[i * d] = -f[i * d]; } for (int i = 0; i <= n + 2; ++i) { if (i >= m) break; g[i] = binom(n + 2, i); if (i & 1) g[i] = -g[i]; } f *= inverse(g); cout << f[m - 1].v << '\n'; }