Makoto and a Blackboard

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;
}