#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; }; //!==================================!// //! 88888888b 88888888b d888888P !// //! 88 88 88 !// //! a88aaaa a88aaaa 88 !// //! 88 88 88 !// //! 88 88 88 !// //! dP dP dP !// //!==================================!// struct C { using F = double; F x{}, y{}; C operator+(const C& c) const { return C{x + c.x, y + c.y}; } C operator-(const C& c) const { return C{x - c.x, y - c.y}; } C operator*(const C& c) const { return C{x * c.x - y * c.y, x * c.y + y * c.x}; } C operator~() const { return C{x, -y}; } }; constexpr std::size_t L = 20; C roots[1 << L] = {{0, 0}, {1, 0}}; std::size_t rev[1 << L] = {0, 1}; C fa[1 << L], fb[1 << L]; template class FFT { private: void fft(C* a, const std::size_t n) const { const std::size_t shift = L - n; for (std::size_t i = 0; i < (1UL << n); i++) { if (i < (rev[i] >> shift)) { std::swap(a[i], a[rev[i] >> shift]); } } for (std::size_t k = 1; k < (1UL << n); k <<= 1) { for (std::size_t i = 0; i < (1UL << n); i += (2 * k)) { for (std::size_t j = 0; j < k; j++) { const C z = a[i + j + k] * roots[j + k]; a[i + j + k] = a[i + j] - z, a[i + j] = a[i + j] + z; } } } } static std::size_t LG(const std::size_t n) { std::size_t lg = 0; for (std::size_t ans = 1; ans < n; ans <<= 1, lg++) {} return lg; } public: FFT() { for (std::size_t i = 0; i < (1 << L); i++) { rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (L - 1)); } for (std::size_t k = 1; k < L; k++) { const F s = 2 * PI() / (1 << (k + 1)); for (std::size_t i = 1UL << (k - 1); i < (1UL << k); i++) { roots[i << 1] = roots[i], roots[i << 1 | 1] = roots[i << 1] * C{std::cos(s), std::sin(s)}; } } } template std::vector convolute(const std::vector& a, const std::vector& b) { const std::size_t need = a.size() + b.size() - 1, lg = LG(need), sz = 1 << lg; for (std::size_t i = 0; i < sz; i++) { fa[i] = C{F(i < a.size() ? a[i] : 0), F(i < b.size() ? b[i] : 0)}; } fft(fa, lg); const C r{0, -0.25 / (F)sz}; for (std::size_t i = 0; i <= (sz >> 1); i++) { std::size_t j = (sz - i) & (sz - 1); const C z = (fa[j] * fa[j] - ~(fa[i] * fa[i])) * r; fa[j] = (fa[i] * fa[i] - ~(fa[j] * fa[j])) * r, fa[i] = z; } fft(fa, lg); std::vector ans(need); for (std::size_t i = 0; i < need; i++) { ans[i] = (T)std::floor(fa[i].x + 0.5); } return ans; } template std::vector convolute(const std::vector& a, const std::vector& b, const T mod) { const std::size_t need = a.size() + b.size() - 1, lg = LG(need), sz = 1 << lg; for (std::size_t i = 0; i < a.size(); i++) { const int x = (mod + a[i] % mod) % mod; fa[i] = C{(F)(x & ((1 << 15) - 1)), F(x >> 15)}; } std::fill(fa + a.size(), fa + sz, C{0, 0}); fft(fa, lg); for (std::size_t i = 0; i < b.size(); i++) { const T x = (mod + b[i] % mod) % mod; fb[i] = C{F(x & ((1 << 15) - 1)), F(x >> 15)}; } std::fill(fb + b.size(), fb + sz, C{0, 0}); fft(fb, lg); F ratio = 0.25 / F(sz); C r2{0, -1}, r3{ratio, 0}, r4{0, -ratio}, r5{0, 1}; for (std::size_t i = 0; i <= (sz >> 1); i++) { const std::size_t j = (sz - i) & (sz - 1); const C a1 = (fa[i] + ~fa[j]), a2 = (fa[i] - ~fa[j]) * r2, b1 = (fb[i] + ~fb[j]) * r3, b2 = (fb[i] - ~fb[j]) * r4; if (i != j) { const C c1 = (fa[j] + ~fa[i]), c2 = (fa[j] - ~fa[i]) * r2, d1 = (fb[j] + ~fb[i]) * r3, d2 = (fb[j] - ~fb[i]) * r4; fa[i] = c1 * d1 + c2 * d2 * r5, fb[i] = c1 * d2 + c2 * d1; } fa[j] = a1 * b1 + a2 * b2 * r5, fb[j] = a1 * b2 + a2 * b1; } fft(fa, lg), fft(fb, lg); std::vector ans(need); for (std::size_t i = 0; i < need; i++) { const T aa = (T)std::floor(fa[i].x + 0.5), bb = (T)std::floor(fb[i].x + 0.5), cc = (T)std::floor(fa[i].y + 0.5); ans[i] = (T)(aa + ((bb % mod) << 15) + ((cc % mod) << 30)) % mod; } return ans; } }; //!============================================!// //! 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() { int N, M, D1, D2; std::cin >> N >> M >> D1 >> D2; const ll D = D2 - D1, L = M - D1 * (N - 1) - 1; if (L < 0) { return std::cout << 0 << std::endl, 0; } using mll = ModInt>; ModComb> modcomb(1000000); std::vector bunbo(L + 1), bunsi(L + 1, 0); for (int i = 0; i <= N - 1 and i * (D + 1) <= L; i++) { bunsi[i * (D + 1)] = (modcomb.comb(N - 1, i) * ((N - i - 1) % 2 == 0 ? 1 : -1))(); } for (int i = 0; i <= N - 1 and i <= L; i++) { bunbo[i] = (modcomb.comb(N - 1, i) * ((N - i - 1) % 2 == 0 ? 1 : -1))(); } std::vector inv(L + 1, 0); inv[0] = (mll(1) / bunbo[0])(); FFT fft; for (int i = 1; i <= L; i *= 2) { auto a = fft.convolute(inv, inv, MOD); if (a.size() > L + 1) { a.resize(L + 1); } auto b = fft.convolute(a, bunbo, MOD); for (int i = 0; i <= L; i++) { inv[i] = (MOD + (inv[i] * 2 - b[i]) % MOD) % MOD; } if (inv.size() > L + 1) { inv.resize(L + 1); } } auto mul = fft.convolute(inv, bunsi, MOD); mul.resize(L + 1); ll ans = 0; for (int i = 0; i <= L; i++) { (ans += mul[i] * (L - i + 1)) %= MOD; } std::cout << ans << std::endl; return 0; }