#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// using ld = long double; using ll = long long; using ull = unsigned long long; std::mt19937 mt{std::random_device{}()}; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr T MOD = static_cast(1000000007); template constexpr F PI() { return 3.1415926535897932385; } #define SHOW(...) (std::cerr << "(" << #__VA_ARGS__ << ") = ("), HogeHogeSansuu(__VA_ARGS__), std::cerr << ")" << std::endl; struct has_debugPrint_impl { template static auto check(T&& x) -> decltype(x.debugPrint(), std::true_type{}); template static auto check(...) -> std::false_type; }; template class has_debugPrint : public decltype(has_debugPrint_impl::check(std::declval())) { }; template struct HogeHogeDump { template static void dump(const T& x) { x.debugPrint(); } }; template <> struct HogeHogeDump { template static void dump(const T& x) { std::cerr << x; } }; void HogeHogeSansuu() { ; } template void HogeHogeSansuu(const T& x) { HogeHogeDump::value>::dump(x); } template void HogeHogeSansuu(const T& x, Args... args) { HogeHogeDump::value>::dump(x), std::cerr << ",", HogeHogeSansuu(args...); } template bool chmin(T& a, const T& b) { return a = std::min(a, b), a == b; } template bool chmax(T& a, const T& b) { return a = std::max(a, b), a == b; } template void For(const T s, const T t, const F f) { for (T i = s; i != t; i += T(s < t ? 1 : -1)) { f(i); } } template void Rep(const T N, const F f) { For(0, N, f); } template void RRep(const T N, const F f) { For(N - 1, -1, f); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T PopCount(const T u) { unsigned long long v = static_cast(u); return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); } template constexpr T log2p1(const T u) { unsigned long long v = static_cast(u); return v = static_cast(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PopCount(v); } template constexpr bool ispow2(const T v) { return (v << 1) == (T(1) << (log2p1(v))); } template constexpr T ceil2(const T v) { return ispow2(v) ? v : T(1) << log2p1(v); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : ispow2(v) ? v : T(1) << (log2p1(v) - 1); } template struct Accum { template Accum(const InIt first, const InIt last) : accum(std::size_t(std::distance(first, last))) { std::partial_sum(first, last, accum.begin()); } T sum(const std::size_t i) const { return i == 0 ? T(0) : accum[i - 1]; } T sum(const std::size_t l, const std::size_t r) const { return sum(r) - sum(l); } std::vector accum; }; template struct Accum2D { Accum2D(const std::vector>& t) : accum{t} { for (std::size_t i = 0; i < accum.size(); i++) { for (std::size_t j = 1; j < accum[i].size(); j++) { accum[i][j] += accum[i][j - 1]; } } for (std::size_t i = 1; i < accum.size(); i++) { for (std::size_t j = 0; j < accum[i].size(); j++) { accum[i][j] += accum[i - 1][j]; } } } T sum(const std::size_t y, const std::size_t x) const { return y == 0 or x == 0 ? T(0) : accum[y - 1][x - 1]; } T sum(const std::size_t ymin, const std::size_t ysup, const std::size_t xmin, const std::size_t xsup) const { return sum(ysup, xsup) - sum(ymin, xmin); } std::vector> accum; }; template struct Zip { template Zip(const InIt first, const InIt last) : unzip(std::size_t(std::distance(first, last))) { std::copy(first, last, unzip), std::sort(unzip.begin(), unzip.end()), unzip.erase(std::unique(unzip.begin(), unzip.end()), unzip.end()); for (std::size_t i = 0; i < unzip.size(); i++) { zip[unzip[i]] = i; } } std::vector unzip; std::map zip; }; template std::ostream& operator<<(std::ostream& os, const std::array& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::deque& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::pair& v) { return (os << "<" << v.first << "," << v.second << ">"); } template std::ostream& operator<<(std::ostream& os, const std::priority_queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.front() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::stack& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::unordered_multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } //!===============================================================!// //! 88888888b dP .88888. a88888b. 888888ba !// //! 88 88 d8' '88 d8' '88 88 '8b !// //! a88aaaa dP. .dP d8888P 88 88 88 88 !// //! 88 '8bd8' 88 88 YP88 88 88 88 !// //! 88 .d88b. 88 Y8. .88 Y8. .88 88 .8P !// //! 88888888P dP' 'dP dP '88888' Y88888P' 8888888P !// //!===============================================================!// template constexpr std::pair extgcd(const T a, const T b) { if (b == 0) { return std::pair{1, 0}; } const auto p = extgcd(b, a % b); return {p.second, p.first - p.second * (a / b)}; } template constexpr T inverse(const T a, const T mod) { return (mod + extgcd((mod + a % mod) % mod, mod).first % mod) % mod; } //!========================================================!// //! 8888ba.88ba dP dP dP !// //! 88 '8b '8b 88 88 88 !// //! 88 88 88 .d8888b. .d888b88 88 88d888b. d8888P !// //! 88 88 88 88' '88 88' '88 88 88' '88 88 !// //! 88 88 88 88. .88 88. .88 88 88 88 88 !// //! dP dP dP '88888P' '88888P8 dP dP dP dP !// //!========================================================!// template class ModInt { private: T value; public: ModInt() : value{0} {} ModInt(const T val) : value{((val % mod) + mod) % mod} {} ModInt(const ModInt& n) : value{n()} {} ModInt& operator=(const ModInt& n) { return value = n(), (*this); } ModInt& operator=(const T v) { return value = (mod + v % mod) % mod, (*this); } ModInt operator+() const { return *this; } ModInt operator-() const { return ModInt{mod - value}; } ModInt operator+(const ModInt& val) const { return ModInt{value + val()}; } ModInt operator-(const ModInt& val) const { return ModInt{value - val() + mod}; } ModInt operator*(const ModInt& val) const { return ModInt{value * val()}; } ModInt operator/(const ModInt& val) const { return ModInt{value * inverse(val(), mod)}; } ModInt& operator+=(const ModInt& val) { return (((value += val()) %= mod) += mod) %= mod, (*this); } ModInt& operator-=(const ModInt& val) { return (((value -= val()) %= mod) += mod) %= mod, (*this); } ModInt& operator*=(const ModInt& val) { return (((value *= val()) %= mod) += mod) %= mod, (*this); } ModInt& operator/=(const ModInt& val) { return (((value *= inverse(val(), mod)) %= mod) += mod) %= mod, (*this); } ModInt operator+(const T val) const { return ModInt{value + val}; } ModInt operator-(const T val) const { return ModInt{value - val}; } ModInt operator*(const T val) const { return ModInt{value * val}; } ModInt operator/(const T val) const { return ModInt{value * inverse(val, mod)}; } template ModInt operator^(const I n) const { return n < 0 ? (T(1) / (*this)) ^ (-n) : n == 0 ? ModInt(1) : n % 2 == 1 ? (*this) * ((*this) ^ (n - 1)) : ((*this * *this) ^ (n / 2)); } ModInt& operator+=(const T val) { return (((value += val) %= mod) += mod) %= mod, (*this); } ModInt& operator-=(const T val) { return (((value -= val) %= mod) += mod) %= mod, (*this); } ModInt& operator*=(const T val) { return (((value *= val) %= mod) += mod) %= mod, (*this); } ModInt& operator/=(const T val) { return (((value *= inverse(val, mod)) %= mod) += mod) %= mod, (*this); } template ModInt& operator^=(const I n) { return (*this) = ((*this) ^ n); } bool operator==(const ModInt& val) const { return value == val.value; } bool operator!=(const ModInt& val) const { return not(*this == val); } bool operator==(const T val) const { return value == (mod + val % mod) % mod; } bool operator!=(const T val) const { return not(*this == val); } T operator()() const { return value; } }; template inline ModInt operator+(const T val, const ModInt& n) { return ModInt{n() + val}; } template inline ModInt operator-(const T val, const ModInt& n) { return ModInt{-n() + val}; } template inline ModInt operator*(const T val, const ModInt& n) { return ModInt{n() * val}; } template inline ModInt operator/(const T val, const ModInt& n) { return ModInt(val) / n; } template inline bool operator==(const T val, const ModInt& n) { return n == val; } template inline bool operator!=(const T val, const ModInt& n) { return not(val == n); } template inline std::istream& operator>>(std::istream& is, ModInt& n) { T v; return is >> v, n = v, is; } template std::ostream& operator<<(std::ostream& os, const ModInt& n) { return (os << n()); } template using Mint = ModInt; template using Mll = ModInt; //!============================================================================!// //! 8888ba.88ba dP a88888b. dP !// //! 88 '8b '8b 88 d8' '88 88 !// //! 88 88 88 .d8888b. .d888b88 88 .d8888b. 88d8b.d8b. 88d888b. !// //! 88 88 88 88' '88 88' '88 88 88' '88 88''88''88 88' '88 !// //! 88 88 88 88. .88 88. .88 Y8. .88 88. .88 88 88 88 88. .88 !// //! dP dP dP '88888P' '88888P8 Y88888P' '88888P' dP dP dP 88Y8888' !// //!============================================================================!// template class ModComb { public: ModComb(const std::size_t N) : f(N + 1, ModInt(1)), in(N + 1, ModInt(1)), invf(N + 1, ModInt(1)) { for (T i = 2; i <= (T)N; i++) { f[i] = f[i - 1] * i, in[i] = (mod - (mod / i)) * in[mod % i], invf[i] = invf[i - 1] * in[i]; } } ModInt fact(const std::size_t N) const { return f[N]; } ModInt inv(const std::size_t N) const { return in[N]; } ModInt invFact(const std::size_t N) const { return invf[N]; } ModInt perm(const std::size_t N, const std::size_t K) const { return f[N] * invf[N - K]; } ModInt comb(const std::size_t N, const std::size_t K) const { return f[N] * invf[K] * invf[N - K]; } private: std::vector> f, in, invf; }; //!============================================!// //! 8888ba.88ba oo !// //! 88 '8b '8b !// //! 88 88 88 .d8888b. dP 88d888b. !// //! 88 88 88 88' '88 88 88' '88 !// //! 88 88 88 88. .88 88 88 88 !// //! dP dP dP '88888P8 dP dP dP !// //!============================================!// int main() { ll N, M, D1, D2; std::cin >> N >> M >> D1 >> D2; const ll D = D2 - D1, L = M - D1 * (N - 1) - 1; using mll = ModInt>; ModComb> mod(L + N); mll ans = 0; for (int i = 0; i <= N - 1 and L >= (D + 1) * i; i++) { mll sum = mod.comb(L - (D + 1) * i + N, N) * mod.comb(N - 1, i); ans += (i % 2 == 0 ? sum : -sum); } std::cout << ans << std::endl; return 0; }