Makoto has a big blackboard with a positive integer $n$ written on it. He will perform the following action exactly $k$ times:
Suppose the number currently written on the blackboard is $v$. He will randomly pick one of the divisors of $v$ (possibly $1$ and $v$) and replace $v$ with this divisor. As Makoto uses his famous random number generator (RNG) and as he always uses $58$ as his generator seed, each divisor is guaranteed to be chosen with equal probability.
He now wonders what is the expected value of the number written on the blackboard after $k$ steps.
It can be shown that this value can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q \not\equiv 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1}$ modulo $10^9+7$.
Input
The only line of the input contains two integers $n$ and $k$ ($1 \leq n \leq 10^{15}$, $1 \leq k \leq 10^4$).
Output
Print a single integer — the expected value of the number on the blackboard after $k$ steps as $P \cdot Q^{-1} \pmod{10^9+7}$ for $P$, $Q$ defined above.
Examples
input
6 1
output
3
input
6 2
output
875000008
input
60 5
output
237178099
Note
In the first example, after one step, the number written on the blackboard is $1$, $2$, $3$ or $6$ — each occurring with equal probability. Hence, the answer is $\frac{1+2+3+6}{4}=3$.
In the second example, the answer is equal to $1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}$.
Solution:
#include <bits/stdc++.h> using namespace std; const int md = (int) 1e9 + 7; inline void add(int &a, int b) { a += b; if (a >= md) a -= md; } inline void sub(int &a, int b) { a -= b; if (a < 0) a += md; } inline int mul(int a, int b) { return (int) ((long long) a * b % md); } inline int power(int a, long long b) { int res = 1; while (b > 0) { if (b & 1) { res = mul(res, a); } a = mul(a, a); b >>= 1; } return res; } inline int inv(int a) { a %= md; if (a < 0) a += md; int b = md, u = 0, v = 1; while (a) { int t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } assert(b == 1); if (u < 0) u += md; return u; } int main() { ios::sync_with_stdio(false); cin.tie(0); long long n; int k; cin >> n >> k; vector<pair<long long, int>> f; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) { int cc = 0; while (n % i == 0) { n /= i; cc++; } f.emplace_back(i, cc); } } if (n > 1) { f.emplace_back(n, 1); } int ans = 1; for (auto& p : f) { int cc = p.second; vector<vector<int>> dp(k + 1, vector<int>(cc + 1, 0)); dp[0][cc] = 1; for (int i = 0; i < k; i++) { for (int j = 0; j <= cc; j++) { int cur = mul(dp[i][j], inv(j + 1)); for (int t = 0; t <= j; t++) { add(dp[i + 1][t], cur); } } } int x = 1; int cur = 0; for (int j = 0; j <= cc; j++) { add(cur, mul(x, dp[k][j])); x = mul(x, (int) (p.first % md)); } ans = mul(ans, cur); } cout << ans << '\n'; return 0; }