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 P/Q where P and Q are coprime integers and Q not≡ 0 \pmod{10^9+7}. Print the value of P ⋅ Q^{-1} modulo 10^9+7.

Input

The only line of the input contains two integers n and k (1 ≤ n ≤ 10^{15}, 1 ≤ k ≤ 10^4).

Output

Print a single integer — the expected value of the number on the blackboard after k steps as P ⋅ 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 (1+2+3+6)/(4)=3.

In the second example, the answer is equal to 1 ⋅ 9/16+2 ⋅ 3/16+3 ⋅ 3/16+6 ⋅ 1/16=15/8.
import java.util.*;
import java.io.*;

public class Practice {
  BufferedReader br;
  PrintWriter out;
  StringTokenizer st;
  boolean eof;
  private static final long MOD = 1000L * 1000L * 1000L + 7;
  private static final int[] dx = {0, -1, 0, 1};
  private static final int[] dy = {1, 0, -1, 0};
  private static final String yes = "Yes";
  private static final String no = "No";

  void solve() {
    int T = 1;
//    int T = nextInt();
    for (int i = 0; i < T; i++) {
      helper();
    }
  }

  List<List<Long>> powers;
  List<List<Long>> probs;
  long combine;
  void helper() {
    long n = nextLong();
    int k = nextInt();
    powers = new ArrayList<>();
    probs = new ArrayList<>();
    Map<Long, Integer> factors = factor(n);
    long[] inv = new long[200];
    inv[1] = 1;
    for (int i = 2; i < inv.length; i++) {
      inv[i] = powMod(i, MOD - 2, MOD);
    }

    for (Map.Entry<Long, Integer> entry : factors.entrySet()) {
      long base = entry.getKey();
      int highest = entry.getValue();
      long[] init = new long[1 + highest];
      init[highest] = 1;
      for (int i = 0; i < k; i++) {
        long[] nxt = new long[1 + highest];
        for (int j = 0; j <= highest; j++) {
          // 1 / (j + 1)
          for (int p = 0; p <= j; p++) {
            long extra = inv[j + 1] * init[j] % MOD;
            nxt[p] += extra;
            if (nxt[p] >= MOD) {
              nxt[p] -= MOD;
            }
          }
        }
        init = nxt;
      }

      List<Long> power = new ArrayList<>();
      List<Long> prob = new ArrayList<>();
      for (long v : init) {
        prob.add(v);
      }
      long start = 1;
      for (int i = 0; i <= highest; i++) {
        power.add(start);
        start = start * base % MOD;
      }

      powers.add(power);
      probs.add(prob);
    }

    combine = 0;
    rec(0, 1L);
    outln(combine % MOD);
  }

  void rec(int idx, long prev) {
    if (idx >= powers.size()) {
      combine += prev;
      if (combine >= MOD) {
        combine -= MOD;
      }
      return;
    }

    List<Long> power = powers.get(idx);
    List<Long> prob = probs.get(idx);
    for (int i = 0; i < power.size(); i++) {
      long nxt = prev * power.get(i) % MOD;
      nxt = nxt * prob.get(i) % MOD;
      rec(idx + 1, nxt);
    }
  }

  // Power Calculate N^M % MOD, N and M can be long (up to 2^64, ~10^18)
  public long powMod(long N, long M, long MOD){//N^M % MOD
    if(M == 0L)
      return 1L;
    long[] hp = new long[64];
    boolean[] bp = new boolean[64];
    hp[0] = N;
    for(int i = 1; i < hp.length; i++) {
      hp[i] = (hp[i - 1] * hp[i - 1]) % MOD;
    }
    for(int j = 0; j < hp.length; j++) {
      if((M & (1L << j)) != 0)
        bp[j] = true;
    }
    long res = 1;
    for(int i = 0;i < bp.length; i++){
      if(bp[i]) {
        res = (res * hp[i]) % MOD;
      }
    }
    return res;
  }

  // factorization of a long num
  public Map<Long, Integer> factor(long N) {
    List<Long> res = new ArrayList<>();
    for (long i = 2; i * i <= N; i++) {
      while (N % i == 0) {
        res.add(i);
        N = N / i;
      }
    }
    if (N != 1L) {
      res.add(N);
    }
    Map<Long, Integer> cnt = new HashMap<>();
    for (long v : res) {
      cnt.put(v, cnt.getOrDefault(v, 0) + 1);
    }
    return cnt;
  }

  void shuffle(long[] a) {
    int n = a.length;
    for(int i = 0; i < n; i++) {
      int r = i + (int) (Math.random() * (n - i));
      long tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;
    }
  }
  long gcd(long a, long b) {
    while(a != 0 && b != 0) {
      long c = b;
      b = a % b;
      a = c;
    }
    return a + b;
  }
  private void outln(Object o) {
      out.println(o);
  }
  private void out(Object o) {
      out.print(o);
  }
  private void formatPrint(double val) {
      outln(String.format("%.9f%n", val));
  }
  public Practice() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);
    solve();
    out.close();
  }
  public static void main(String[] args) {
    new Practice();
  }

  public long[] nextLongArr(int n) {
    long[] res = new long[n];
    for(int i = 0; i < n; i++)
      res[i] = nextLong();
    return res;
  }
  public int[] nextIntArr(int n) {
    int[] res = new int[n];
    for(int i = 0; i < n; i++)
      res[i] = nextInt();
    return res;
  }
  public String nextToken() {
    while (st == null || !st.hasMoreTokens()) {
      try {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) {
        eof = true;
        return null;
      }
    }
    return st.nextToken();
  }
  public String nextString() {
    try {
      return br.readLine();
    } catch (IOException e) {
      eof = true;
      return null;
    }
  }
  public int nextInt() {
    return Integer.parseInt(nextToken());
  }
  public long nextLong() {
    return Long.parseLong(nextToken());
  }
  public double nextDouble() {
    return Double.parseDouble(nextToken());
  }
}