#line 1 "main.cpp" #include #line 2 "library/src/math/static_modint.hpp" #include #include #line 3 "library/src/math/gcd.hpp" #include namespace kyopro { template constexpr T inline _gcd(T a, T b) { assert(a >= 0 && b >= 0); if (a == 0 || b == 0) return a + b; int d = std::min(__builtin_ctzll(a), __builtin_ctzll(b)); a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b); while (a != b) { if (!a||!b) { return a + b; } if (a >= b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template constexpr T ext_gcd(T a, T b, T& x, T& y) { x = 1, y = 0; T nx = 0, ny = 1; while (b) { T q = a / b; std::tie(a, b) = std::pair{b, a % b}; std::tie(x, nx) = std::pair{nx, x - nx * q}; std::tie(y, ny) = std::pair{ny, y - ny * q}; } return a; } }; // namespace kyopro #line 5 "library/src/math/static_modint.hpp" namespace kyopro { template <__uint64_t mod> class static_modint { private: using mint = static_modint; using i64 = long long; using u64 = unsigned long long; using u128 = __uint128_t; using i128 = __int128_t; u64 v; constexpr inline u64 normalize(i64 v_) const { v_ %= mod; if (v_ < 0) { v_ += mod; } return v_; } public: constexpr static_modint() : v(0) {} constexpr static_modint(i64 v_) : v(normalize(v_)) {} // operator constexpr u64 val() const { return v; } constexpr mint& operator+=(const mint& rhs) { v += rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator-=(const mint& rhs) { v += mod - rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator*=(const mint& rhs) { v = (u128)v * rhs.val() % mod; return (*this); } constexpr mint operator+(const mint& r) const { return mint(*this) += r; } constexpr mint operator-(const mint& r) const { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const { return mint(*this) *= r; } constexpr mint& operator+=(const i64& rhs) { (*this) += mint(rhs); return (*this); } constexpr mint& operator-=(const i64& rhs) { (*this) -= mint(rhs); return (*this); } constexpr mint& operator*=(const i64& rhs) { (*this) *= mint(rhs); return (*this); } constexpr friend mint operator+(const i64& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(const i64& l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(const i64& l, const mint& r) { return mint(l) *= r; } constexpr mint operator+(i64 r) { return mint(*this) += r; } constexpr mint operator-(i64 r) { return mint(*this) -= r; } constexpr mint operator*(i64 r) { return mint(*this) *= r; } constexpr mint& operator=(i64 r) { return (*this) = mint(r); } constexpr bool operator==(const mint& r) const { return (*this).val() == r.val(); } template constexpr mint pow(T e) const { mint ans(1), base(*this); while (e) { if (e & 1) { ans *= base; } base *= base; e >>= 1; } return ans; } constexpr inline mint inv() const { long long x, y; auto d = ext_gcd((long long)mod, (long long)v, x, y); assert(d == 1); return mint(y); } constexpr mint& operator/=(const mint& r) { return (*this) *= r.inv(); } constexpr mint inv(const mint& r) const { return mint(*this) *= r.inv(); } constexpr friend mint operator/(const mint& l, i64 r) { return mint(l) /= mint(r); } constexpr friend mint operator/(i64 l, const mint& r) { return mint(l) /= mint(r); } // iostream constexpr friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } constexpr friend std::istream& operator>>(std::istream& is, mint& mt) { i64 v_; is >> v_; mt = v_; return is; } }; template <__uint32_t mod> class static_modint32 { private: using mint = static_modint32; using i32 = __int32_t; using u32 = __uint32_t; using i64 = __int64_t; using u64 = __uint64_t; u32 v; constexpr inline u32 normalize(i64 v_) const { v_ %= mod; if (v_ < 0) { v_ += mod; } return v_; } public: constexpr static_modint32() : v(0) {} constexpr static_modint32(const i64& v_) : v(normalize(v_)) {} // operator static mint raw(u32 a){ mint m; m.v = a; return m; } constexpr u32 val() const { return v; } constexpr mint& operator+=(const mint& rhs) { v += rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator-=(const mint& rhs) { v += mod - rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator*=(const mint& rhs) { v = (u64)v * rhs.val() % mod; return (*this); } constexpr mint operator+(const mint& r) const { return mint(*this) += r; } constexpr mint operator-(const mint& r) const { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const { return mint(*this) *= r; } constexpr mint& operator+=(const i64& rhs) { (*this) += mint(rhs); return (*this); } constexpr mint& operator-=(const i64& rhs) { (*this) -= mint(rhs); return (*this); } constexpr mint& operator*=(const i64& rhs) { (*this) *= mint(rhs); return (*this); } constexpr friend mint operator+(const i64& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(i64 l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(i64 l, const mint& r) { return mint(l) *= r; } constexpr mint operator+(i64 r) { return mint(*this) += r; } constexpr mint operator-(i64 r) { return mint(*this) -= r; } constexpr mint operator*(i64 r) { return mint(*this) *= r; } constexpr mint& operator=(i64 r) { return (*this) = mint(r); } constexpr bool operator==(const mint& r) const { return (*this).val() == r.val(); } template constexpr mint pow(T e) const { mint ans(1), base(*this); while (e) { if (e & 1) { ans *= base; } base *= base; e >>= 1; } return ans; } constexpr inline mint inv() const { long long x, y; auto d = ext_gcd((long long)mod, (long long)v, x, y); assert(d == 1); return mint(y); } constexpr mint& operator/=(const mint& r) { return (*this) *= r.inv(); } constexpr mint operator/(const mint& r) const { return mint(*this) *= r.inv(); } constexpr friend mint operator/(const mint& l, i64 r) { return mint(l) /= mint(r); } constexpr friend mint operator/(i64 l, const mint& r) { return mint(l) /= mint(r); } // iostream constexpr friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } constexpr friend std::istream& operator>>(std::istream& is, mint& mt) { i64 v_; is >> v_; mt = v_; return is; } }; }; // namespace kyopro /// @brief modint /// @docs docs/math/static_modint.md #line 2 "library/src/template.hpp" #include #define rep(i, N) for (int i = 0; i < (N); i++) #define all(x) (x).begin(),(x).end() #define popcount(x) __builtin_popcount(x) using i128=__int128_t; using ll = long long; using ld = long double; using graph = std::vector>; using P = std::pair; constexpr int inf = 1e9; constexpr ll infl = 1e18; constexpr ld eps = 1e-6; const long double pi = acos(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = { 1,0,-1,0 }; constexpr int dy[] = { 0,1,0,-1 }; templateconstexpr inline void chmax(T&x,T y){if(xconstexpr inline void chmin(T&x,T y){if(x>y)x=y;} #line 4 "main.cpp" using namespace std; using mint = atcoder::modint1000000007; constexpr int MAX = 3e5; mint fac[MAX], finv[MAX], inv[MAX]; const int NUM_FAC = 2000001; ll modfact(ll x) { static ll _fact[NUM_FAC + 1]; if (_fact[0] == 0) { _fact[0] = 1; for (int i = 1; i <= NUM_FAC; ++i) _fact[i] = _fact[i - 1] * i % MOD; } return _fact[x]; } ll modpow(ll a, ll n) { ll r = 1; while (n) r = r * ((n % 2) ? a : 1) % MOD, a = a * a % MOD, n >>= 1; return r; } ll moddiv(ll a, ll b) { ll ap_2 = modpow(b, MOD - 2); return (a * ap_2) % MOD; } ll aCb(ll a, ll b) { return moddiv(modfact(a), (modfact(a - b) * modfact(b)) % MOD); } int main() { ll n, m; cin >> n >> m; if (n < m) { puts("0"); return 0; } mint ans = 0; mint p = -1; for (int c = m; c >= 1; --c) { ans += (p *= -1) * aCb(m, c) * (mint(c).pow(n)); } cout << ans.val() << '\n'; }