#line 1 "main.cpp" #include #line 2 "/home/ubuntu/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "/home/ubuntu/Library/modulus/modpow.hpp" inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) { assert (/* 0 <= x and */ x < (uint_fast64_t)MOD); uint_fast64_t y = 1; for (; k; k >>= 1) { if (k & 1) (y *= x) %= MOD; (x *= x) %= MOD; } assert (/* 0 <= y and */ y < (uint_fast64_t)MOD); return y; } #line 5 "/home/ubuntu/Library/modulus/modinv.hpp" inline int32_t modinv_nocheck(int32_t value, int32_t MOD) { assert (0 <= value and value < MOD); if (value == 0) return -1; int64_t a = value, b = MOD; int64_t x = 0, y = 1; for (int64_t u = 1, v = 0; a; ) { int64_t q = b / a; x -= q * u; std::swap(x, u); y -= q * v; std::swap(y, v); b -= q * a; std::swap(b, a); } if (not (value * x + MOD * y == b and b == 1)) return -1; if (x < 0) x += MOD; assert (0 <= x and x < MOD); return x; } inline int32_t modinv(int32_t x, int32_t MOD) { int32_t y = modinv_nocheck(x, MOD); assert (y != -1); return y; } #line 6 "/home/ubuntu/Library/modulus/mint.hpp" /** * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ */ template struct mint { int32_t value; mint() : value() {} mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {} mint(int32_t value_, std::nullptr_t) : value(value_) {} explicit operator bool() const { return value; } inline mint operator + (mint other) const { return mint(*this) += other; } inline mint operator - (mint other) const { return mint(*this) -= other; } inline mint operator * (mint other) const { return mint(*this) *= other; } inline mint & operator += (mint other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } inline mint & operator -= (mint other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } inline mint & operator *= (mint other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; } inline mint operator - () const { return mint(this->value ? MOD - this->value : 0, nullptr); } inline bool operator == (mint other) const { return value == other.value; } inline bool operator != (mint other) const { return value != other.value; } inline mint pow(uint64_t k) const { return mint(modpow(value, k, MOD), nullptr); } inline mint inv() const { return mint(modinv(value, MOD), nullptr); } inline mint operator / (mint other) const { return *this * other.inv(); } inline mint & operator /= (mint other) { return *this *= other.inv(); } }; template mint operator + (int64_t value, mint n) { return mint(value) + n; } template mint operator - (int64_t value, mint n) { return mint(value) - n; } template mint operator * (int64_t value, mint n) { return mint(value) * n; } template mint operator / (int64_t value, mint n) { return mint(value) / n; } template std::istream & operator >> (std::istream & in, mint & n) { int64_t value; in >> value; n = value; return in; } template std::ostream & operator << (std::ostream & out, mint n) { return out << n.value; } #line 7 "/home/ubuntu/Library/number/primes.hpp" struct prepared_primes { int size; std::vector sieve; std::vector primes; /** * @note O(size) */ prepared_primes(int size_) : size(size_) { sieve.resize(size); REP3 (p, 2, size) if (sieve[p] == 0) { primes.push_back(p); for (int k = p; k < size; k += p) { if (sieve[k] == 0) { sieve[k] = p; } } } } /** * @note let k be the length of the result, O(k) if n < size; O(\sqrt{n} + k) if size <= n < size^2 */ std::vector list_prime_factors(int64_t n) const { assert (1 <= n and n < (int64_t)size * size); std::vector result; // trial division for large part for (int p : primes) { if (n < size or n < (int64_t)p * p) { break; } while (n % p == 0) { n /= p; result.push_back(p); } } // small part if (n == 1) { // nop } else if (n < size) { while (n != 1) { result.push_back(sieve[n]); n /= sieve[n]; } } else { result.push_back(n); } assert (std::is_sorted(ALL(result))); return result; } std::vector list_all_factors(int64_t n) const { auto p = list_prime_factors(n); std::vector d; d.push_back(1); for (int l = 0; l < p.size(); ) { int r = l + 1; while (r < p.size() and p[r] == p[l]) ++ r; int n = d.size(); REP (k1, r - l) { REP (k2, n) { d.push_back(d[d.size() - n] * p[l]); } } l = r; } return d; } /** * @note O(1) if n < size; O(sqrt n) if size <= n < size^2 */ bool is_prime(int64_t n) const { assert (1 <= n and n < (int64_t)size * size); if (n < size) { return sieve[n] == n; } for (int p : primes) { if (n < (int64_t)p * p) { break; } if (n % p == 0) { return false; } } return true; } }; #line 7 "/home/ubuntu/Library/number/primes_extra.hpp" std::map list_prime_factors_as_map(const prepared_primes& primes, int64_t n) { std::map cnt; for (int64_t p : primes.list_prime_factors(n)) { ++ cnt[p]; } return cnt; } int64_t euler_totient(const prepared_primes& primes, int64_t n) { int64_t phi = 1; int64_t last = -1; for (int64_t p : primes.list_prime_factors(n)) { if (last != p) { last = p; phi *= p - 1; } else { phi *= p; } } return phi; } #line 5 "/home/ubuntu/Library/modulus/choose_simple.hpp" /** * @brief combination / 組合せ ${} _ n C _ r$ (愚直 $O(r)$) */ template mint choose_simple(int64_t n, int32_t r) { assert (0 <= r and r <= n); mint num = 1; mint den = 1; REP (i, r) { num *= n - i; den *= i + 1; } return num / den; } #line 5 "/home/ubuntu/Library/modulus/multichoose_simple.hpp" /** * @brief 重複組合せ ${} _ n H _ r = {} _ {n + r - 1} C _ r$ (愚直 $O(r)$) */ template mint multichoose_simple(int64_t n, int32_t r) { assert (0 <= n and 0 <= r); if (n == 0 and r == 0) return 1; return choose_simple(n + r - 1, r); } #line 7 "main.cpp" using namespace std; prepared_primes primes(1e6 + 100); constexpr int64_t MOD = 1000000007; mint solve(int64_t n, int64_t k) { mint ans = 1; for (auto [p, e] : list_prime_factors_as_map(primes, n)) { // ans *= multichoose_simple(k, e); mint y = 0; REP (x, e + 1) { y += multichoose_simple(k, x); } ans *= y; } return ans; } // generated by oj-template v4.8.0 (https://github.com/online-judge-tools/template-generator) int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int64_t N, K; std::cin >> N >> K; auto ans = solve(N, K); std::cout << ans << '\n'; return 0; }