Let's introduce some definitions that will be needed later.

Let prime(x) be the set of prime divisors of x. For example, prime(140) = \{ 2, 5, 7 \}, prime(169) = \{ 13 \}.

Let g(x, p) be the maximum possible integer p^k where k is an integer such that x is divisible by p^k. For example:

  * g(45, 3) = 9 (45 is divisible by 3^2=9 but not divisible by 3^3=27), 
  * g(63, 7) = 7 (63 is divisible by 7^1=7 but not divisible by 7^2=49). 



Let f(x, y) be the product of g(y, p) for all p in prime(x). For example:

  * f(30, 70) = g(70, 2) ⋅ g(70, 3) ⋅ g(70, 5) = 2^1 ⋅ 3^0 ⋅ 5^1 = 10, 
  * f(525, 63) = g(63, 3) ⋅ g(63, 5) ⋅ g(63, 7) = 3^2 ⋅ 5^0 ⋅ 7^1 = 63. 



You have integers x and n. Calculate f(x, 1) ⋅ f(x, 2) ⋅ … ⋅ f(x, n) mod{(10^{9} + 7)}.

Input

The only line contains integers x and n (2 ≤ x ≤ 10^{9}, 1 ≤ n ≤ 10^{18}) — the numbers used in formula.

Output

Print the answer.

Examples

Input


10 2


Output


2


Input


20190929 1605


Output


363165664


Input


947 987654321987654321


Output


593574252

Note

In the first example, f(10, 1) = g(1, 2) ⋅ g(1, 5) = 1, f(10, 2) = g(2, 2) ⋅ g(2, 5) = 2.

In the second example, actual value of formula is approximately 1.597 ⋅ 10^{171}. Make sure you print the answer modulo (10^{9} + 7).

In the third example, be careful about overflow issue.
#include <bits/stdc++.h>
using namespace std;
struct initon {
  initon() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    srand((unsigned)clock() + (unsigned)time(NULL));
  };
} __initon;
struct T {
  int f, s, t;
  T() { f = -1, s = -1, t = -1; }
  T(int f, int s, int t) : f(f), s(s), t(t) {}
  bool operator<(const T &r) const {
    return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t;
  }
  bool operator>(const T &r) const {
    return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t;
  }
  bool operator==(const T &r) const { return f == r.f && s == r.s && t == r.t; }
  bool operator!=(const T &r) const { return f != r.f || s != r.s || t != r.t; }
  int operator[](int i) {
    assert(i < 3);
    return i == 0 ? f : i == 1 ? s : t;
  }
};
using dou = long double;
using itn = long long;
using str = string;
using bo = bool;
using P = pair<long long, long long>;
using vi = vector<long long>;
using vl = vector<long long>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<long double>;
using vc = vector<char>;
using vp = vector<P>;
using vt = vector<T>;
using mapi = map<long long, long long>;
using mapd = map<dou, long long>;
using mapc = map<char, long long>;
using maps = map<str, long long>;
using seti = set<long long>;
using setd = set<dou>;
using setc = set<char>;
using sets = set<str>;
using qui = queue<long long>;
const long long inf = (long long)1e9 + 100;
const long long linf = (long long)1e18 + 100;
const long double eps = 1e-9;
const long double PI = 3.1415926535897932384626433832795029L;
long long ma = numeric_limits<long long>::min();
long long mi = numeric_limits<long long>::max();
const long long y4[] = {-1, 1, 0, 0};
const long long x4[] = {0, 0, -1, 1};
const long long y8[] = {0, 1, 0, -1, -1, 1, 1, -1};
const long long x8[] = {1, 0, -1, 0, 1, -1, 1, -1};
inline void sort(string &a) { sort(a.begin(), a.end()); }
template <class T>
inline void sort(vector<T> &a) {
  sort(a.begin(), a.end());
};
template <class T>
inline void sort(vector<T> &a, long long len) {
  sort(a.begin(), a.begin() + len);
};
template <class T, class F>
inline void sort(vector<T> &a, F f) {
  sort(a.begin(), a.end(), [&](T l, T r) { return f(l) < f(r); });
};
enum ___pcomparator { fisi, fisd, fdsi, fdsd, sifi, sifd, sdfi, sdfd };
inline void sort(vector<P> &a, ___pcomparator type) {
  switch (type) {
    case fisi:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.first != r.first ? l.first < r.first : l.second < r.second;
      });
      break;
    case fisd:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.first != r.first ? l.first < r.first : l.second > r.second;
      });
      break;
    case fdsi:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.first != r.first ? l.first > r.first : l.second < r.second;
      });
      break;
    case fdsd:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.first != r.first ? l.first > r.first : l.second > r.second;
      });
      break;
    case sifi:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.second != r.second ? l.second < r.second : l.first < r.first;
      });
      break;
    case sifd:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.second != r.second ? l.second < r.second : l.first > r.first;
      });
      break;
    case sdfi:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.second != r.second ? l.second > r.second : l.first < r.first;
      });
      break;
    case sdfd:
      sort((a).begin(), (a).end(), [&](P l, P r) {
        return l.second != r.second ? l.second > r.second : l.first > r.first;
      });
      break;
  }
};
inline void sort(vector<T> &a, ___pcomparator type) {
  switch (type) {
    case fisi:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.f != r.f ? l.f < r.f : l.s < r.s; });
      break;
    case fisd:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.f != r.f ? l.f < r.f : l.s > r.s; });
      break;
    case fdsi:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.f != r.f ? l.f > r.f : l.s < r.s; });
      break;
    case fdsd:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.f != r.f ? l.f > r.f : l.s > r.s; });
      break;
    case sifi:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.s != r.s ? l.s < r.s : l.f < r.f; });
      break;
    case sifd:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.s != r.s ? l.s < r.s : l.f > r.f; });
      break;
    case sdfi:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.s != r.s ? l.s > r.s : l.f < r.f; });
      break;
    case sdfd:
      sort((a).begin(), (a).end(),
           [&](T l, T r) { return l.s != r.s ? l.s > r.s : l.f > r.f; });
      break;
  }
};
template <class T>
inline void rsort(vector<T> &a) {
  sort(a.begin(), a.end(), greater<T>());
};
template <class T>
inline void rsort(vector<T> &a, long long len) {
  sort(a.begin(), a.begin() + len, greater<T>());
};
template <class U, class F>
inline void rsort(vector<U> &a, F f) {
  sort(a.begin(), a.end(), [&](U l, U r) { return f(l) > f(r); });
};
template <class U>
inline void sortp(vector<U> &a, vector<U> &b) {
  vp c;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  for (long long i = 0, _lim = n; i < _lim; i++) c.emplace_back(a[i], b[i]);
  sort(c);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = c[i].first;
    b[i] = c[i].second;
    ;
  }
};
template <class U, class F>
inline void sortp(vector<U> &a, vector<U> &b, F f) {
  vp c;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  for (long long i = 0, _lim = n; i < _lim; i++) c.emplace_back(a[i], b[i]);
  sort(c, f);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = c[i].first;
    b[i] = c[i].second;
  }
};
template <class U, class F>
inline void sortp(vector<U> &a, vector<U> &b, char type) {
  vp c;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  for (long long i = 0, _lim = n; i < _lim; i++) c.emplace_back(a[i], b[i]);
  sort(c, type);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = c[i].first;
    b[i] = c[i].second;
  }
};
template <class U>
inline void rsortp(vector<U> &a, vector<U> &b) {
  vp c;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  for (long long i = 0, _lim = n; i < _lim; i++) c.emplace_back(a[i], b[i]);
  rsort(c);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = c[i].first;
    b[i] = c[i].second;
  }
};
template <class U, class F>
inline void rsortp(vector<U> &a, vector<U> &b, F f) {
  vp c;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  for (long long i = 0, _lim = n; i < _lim; i++) c.emplace_back(a[i], b[i]);
  rsort(c, f);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = c[i].first;
    b[i] = c[i].second;
  }
};
template <class U>
inline void sortt(vector<U> &a, vector<U> &b, vector<U> &c) {
  vt r;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  assert(n == ((long long)(c).size()));
  for (long long i = 0, _lim = n; i < _lim; i++)
    r.emplace_back(a[i], b[i], c[i]);
  sort(r);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = r[i].f;
    b[i] = r[i].s;
    c[i] = r[i].t;
  }
};
template <class U, class F>
inline void sortt(vector<U> &a, vector<U> &b, vector<U> &c, F f) {
  vt r;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  assert(n == ((long long)(c).size()));
  for (long long i = 0, _lim = n; i < _lim; i++)
    r.emplace_back(a[i], b[i], c[i]);
  sort(r, f);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = r[i].f;
    b[i] = r[i].s;
    c[i] = r[i].t;
  }
};
template <class U, class F>
inline void rsortt(vector<U> &a, vector<U> &b, vector<U> &c, F f) {
  vt r;
  long long n = ((long long)(a).size());
  assert(n == ((long long)(b).size()));
  assert(n == ((long long)(c).size()));
  for (long long i = 0, _lim = n; i < _lim; i++)
    r.emplace_back(a[i], b[i], c[i]);
  rsort(r, f);
  for (long long i = 0, _lim = n; i < _lim; i++) {
    a[i] = r[i].f;
    b[i] = r[i].s;
    c[i] = r[i].t;
  }
};
template <class T>
inline void sort2(vector<vector<T>> &a) {
  for (long long i = 0, n = a.size(); i < n; i++) sort(a[i]);
}
template <class T>
inline void rsort2(vector<vector<T>> &a) {
  for (long long i = 0, n = a.size(); i < n; i++) rsort(a[i]);
}
template <typename A, size_t N, typename T>
void fill(A (&a)[N], const T &v) {
  for (long long i = 0, _lim = N; i < _lim; i++) a[i] = v;
}
template <typename A, size_t N, size_t O, typename T>
void fill(A (&a)[N][O], const T &v) {
  for (long long i = 0, _lim = N; i < _lim; i++)
    for (long long j = 0, _lim = O; j < _lim; j++) a[i][j] = v;
}
template <typename A, size_t N, size_t O, size_t P, typename T>
void fill(A (&a)[N][O][P], const T &v) {
  for (long long i = 0, _lim = N; i < _lim; i++)
    for (long long j = 0, _lim = O; j < _lim; j++)
      for (long long k = 0, _lim = P; k < _lim; k++) a[i][j][k] = v;
}
template <typename A, size_t N, size_t O, size_t P, size_t Q, typename T>
void fill(A (&a)[N][O][P][Q], const T &v) {
  for (long long i = 0, _lim = N; i < _lim; i++)
    for (long long j = 0, _lim = O; j < _lim; j++)
      for (long long k = 0, _lim = P; k < _lim; k++)
        for (long long l = 0, _lim = Q; l < _lim; l++) a[i][j][k][l] = v;
}
template <typename A, size_t N, size_t O, size_t P, size_t Q, size_t R,
          typename T>
void fill(A (&a)[N][O][P][Q][R], const T &v) {
  for (long long i = 0, _lim = N; i < _lim; i++)
    for (long long j = 0, _lim = O; j < _lim; j++)
      for (long long k = 0, _lim = P; k < _lim; k++)
        for (long long l = 0, _lim = Q; l < _lim; l++)
          for (long long m = 0, _lim = R; m < _lim; m++) a[i][j][k][l][m] = v;
}
template <typename A, size_t N, size_t O, size_t P, size_t Q, size_t R,
          size_t S, typename T>
void fill(A (&a)[N][O][P][Q][R][S], const T &v) {
  for (long long i = 0, _lim = N; i < _lim; i++)
    for (long long j = 0, _lim = O; j < _lim; j++)
      for (long long k = 0, _lim = P; k < _lim; k++)
        for (long long l = 0, _lim = Q; l < _lim; l++)
          for (long long m = 0, _lim = R; m < _lim; m++)
            for (long long n = 0, _lim = S; n < _lim; n++)
              a[i][j][k][l][m][n] = v;
}
template <typename V, typename T>
void fill(V &xx, const T vall) {
  xx = vall;
}
template <typename V, typename T>
void fill(vector<V> &vecc, const T vall) {
  for (auto &&vx : vecc) fill(vx, vall);
}
template <typename T = long long>
T _in() {
  T x;
  cin >> x;
  return (x);
}
string sin() { return _in<string>(); }
long long lin() { return _in<long long>(); }
void ole() {
  string a = "a";
  for (long long i = 0, _lim = 30; i < _lim; i++) a += a;
  for (long long i = 0, _lim = 1 << 17; i < _lim; i++) cout << a << endl;
  cout << "OLE 出力長制限超過" << endl;
  exit(0);
}
void tle() {
  while (inf) cout << inf << endl;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long gcd(vi b) {
  long long res = b[0];
  for (auto &&v : b) res = gcd(v, res);
  return res;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long rev(long long a) {
  long long res = 0;
  while (a) {
    res *= 10;
    res += a % 10;
    a /= 10;
  }
  return res;
}
template <class T>
void rev(vector<T> &a) {
  reverse((a).begin(), (a).end());
}
void rev(string &a) { reverse((a).begin(), (a).end()); }
long long ceil(long long a, long long b) {
  if (b == 0) {
    cerr << "ceil"
         << " "
         << "(L:" << 583 << ")" << '\n';
    cerr << "a"
         << " = " << a << ", "
         << "b"
         << " = " << b << endl;
    ole();
    return -1;
  } else
    return (a + b - 1) / b;
}
long long sqrt(long long a) {
  if (a < 0) {
    cerr << "sqrt"
         << " "
         << "(L:" << 592 << ")" << '\n';
    cerr << "a"
         << " = " << a << endl;
    ole();
  }
  long long res = (long long)std::sqrt(a);
  while (res * res < a) res++;
  return res;
}
long double log(long double e, long double x) { return log(x) / log(e); }
long long sig(long long t) { return (1 + t) * t / 2; }
long long sig(long long s, long long t) { return (s + t) * (t - s + 1) / 2; }
vi divisors(long long v) {
  vi res;
  long double lim = std::sqrt(v);
  for (long long i = 1; i <= lim; ++i) {
    if (v % i == 0) {
      res.push_back(i);
      if (i != v / i) res.push_back(v / i);
    }
  }
  return res;
}
vb isPrime;
vi primes;
void setPrime() {
  long long len = 4010101;
  isPrime.resize(4010101);
  fill(isPrime, true);
  isPrime[0] = isPrime[1] = false;
  for (long long i = 2; i <= sqrt(len) + 5; ++i) {
    if (!isPrime[i]) continue;
    for (long long j = 2; i * j < len; ++j) {
      isPrime[i * j] = false;
    }
  }
  for (long long i = 0, _lim = len; i < _lim; i++)
    if (isPrime[i]) primes.push_back(i);
}
vi factorization(long long v) {
  long long tv = v;
  vi res;
  if (isPrime.size() == 0) setPrime();
  for (auto &&p : primes) {
    if (v % p == 0) res.push_back(p);
    while (v % p == 0) {
      v /= p;
    }
    if (v == 1 || p * p > tv) break;
  }
  if (v > 1) res.push_back(v);
  return res;
}
inline bool inside(long long h, long long w, long long H, long long W) {
  return h >= 0 && w >= 0 && h < H && w < W;
}
inline bool inside(long long v, long long l, long long r) {
  return l <= v && v < r;
}
long long u(long long a) { return a < 0 ? 0 : a; }
template <class T>
vector<T> u(const vector<T> &a) {
  vector<T> ret = a;
  for (auto &&v : ret) v = u(v);
  return ret;
}
void yn(bool a) {
  if (a)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
}
void Yn(bool a) {
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
void YN(bool a) {
  if (a)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
void fyn(bool a) {
  if (a)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
  exit(0);
}
void fYn(bool a) {
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  exit(0);
}
void fYN(bool a) {
  if (a)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  exit(0);
}
void Possible(bool a) {
  if (a)
    cout << "Possible" << endl;
  else
    cout << "Impossible" << endl;
  exit(0);
}
void POSSIBLE(bool a) {
  if (a)
    cout << "POSSIBLE" << endl;
  else
    cout << "IMPOSSIBLE" << endl;
  exit(0);
}
template <class T, class U>
set<T> &operator+=(set<T> &a, U v) {
  a.insert(v);
  return a;
}
template <class T, class U>
vector<T> &operator+=(vector<T> &a, U v) {
  a.push_back(v);
  return a;
}
template <class T>
T sum(vector<T> &v, long long s = 0, long long t = inf) {
  T ret = 0;
  for (long long i = s, _lim = min(((long long)(v).size()), t); i < _lim; i++)
    ret += v[i];
  return ret;
}
void mod(long long &a, long long m) { a = (a % m + m) % m; }
template <class F>
inline long long mgr(long long ok, long long ng, F f) {
  if (ok < ng)
    while (ng - ok > 1) {
      long long mid = (ok + ng) / 2;
      if (f(mid))
        ok = mid;
      else
        ng = mid;
    }
  else
    while (ok - ng > 1) {
      long long mid = (ok + ng) / 2;
      if (f(mid))
        ok = mid;
      else
        ng = mid;
    }
  return ok;
}
template <class F>
inline long long mgr(long long ok, long long ng, long long second, F f) {
  if (ok < ng)
    while (ng - ok > 1) {
      long long mid = (ok + ng) / 2;
      if (f(mid, second))
        ok = mid;
      else
        ng = mid;
    }
  else
    while (ok - ng > 1) {
      long long mid = (ok + ng) / 2;
      if (f(mid, second))
        ok = mid;
      else
        ng = mid;
    }
  return ok;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &m) {
  for (auto &&v : m) os << v << " ";
  return os;
}
constexpr bool bget(long long m, long long keta) { return (m >> keta) & 1; }
long long bget(long long m, long long keta, long long sinsuu) {
  m /= (long long)pow(sinsuu, keta);
  return m % sinsuu;
}
long long bit(long long n) { return (1LL << (n)); }
long long bit(long long n, long long sinsuu) {
  return (long long)pow(sinsuu, n);
}
long long mask(long long n) { return (1ll << n) - 1; }
template <class T>
vector<T> ruiv(vector<T> &a) {
  vector<T> ret(a.size() + 1);
  for (long long i = 0, _lim = a.size(); i < _lim; i++)
    ret[i + 1] = ret[i] + a[i];
  return ret;
}
template <class T, class U>
inline bool chma(T &a, const U &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class U>
inline bool chma(const U &b) {
  return chma(ma, b);
}
template <class T, class U>
inline bool chmi(T &a, const U &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <class U>
inline bool chmi(const U &b) {
  return chmi(mi, b);
}
long long max(vi &a) {
  long long res = a[0];
  for (auto &&v : a) {
    res = max(res, v);
  }
  return res;
}
long long min(vi &a) {
  long long res = a[0];
  for (auto &&v : a) {
    res = min(res, v);
  }
  return res;
}
long long n, m, k, d, H, W, x, y, z, q;
long long cou;
vi a, b, c;
vector<vi> s(0, vi(0));
vector<vc> ba(0, vc(0));
vp p;
template <typename T>
T minv(T a, T m);
template <typename T>
T minv(T a);
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U &x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U &x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type &operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular &operator+=(const Modular &other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular &operator-=(const Modular &other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular &operator+=(const U &other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular &operator-=(const U &other) {
    return *this -= Modular(other);
  }
  Modular &operator++() { return *this += 1; }
  Modular &operator--() { return *this -= 1; }
  Modular operator++(signed) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(signed) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, signed>::value,
                     Modular>::type &
  operator*=(const Modular &rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type &
  operator*=(const Modular &rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type &
  operator*=(const Modular &rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular &operator/=(const Modular &other) {
    return *this *= Modular(minv(other.value));
  }
  template <typename U>
  friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
  template <typename U>
  friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
  template <typename U>
  friend std::istream &operator>>(std::istream &stream, Modular<U> &number);
  operator long long() { return value; }

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) /= rhs;
}
constexpr signed MOD = 1e9 + 7;
using mint = Modular<std::integral_constant<decay<decltype(MOD)>::type, MOD>>;
constexpr long long mint_len = 1400001;
vi fac, finv, inv;
vi p2;
mint com(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  return mint(finv[r] * fac[n] % MOD * finv[n - r]);
}
mint pom(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  return mint(fac[n] * finv[n - 1]);
}
mint npr(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  return mint(fac[n] * finv[n - r]);
}
long long nprin(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  return fac[n] * finv[n - r] % MOD;
}
long long icom(long long n, long long r) {
  const long long NUM_ = 1400001;
  static long long fac[NUM_ + 1], finv[NUM_ + 1], inv[NUM_ + 1];
  if (fac[0] == 0) {
    inv[1] = fac[0] = finv[0] = 1;
    for (long long i = 2; i <= NUM_; ++i)
      inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    for (long long i = 1; i <= NUM_; ++i)
      fac[i] = fac[i - 1] * i % MOD, finv[i] = finv[i - 1] * inv[i] % MOD;
  }
  if (r < 0 || r > n) return 0;
  return ((finv[r] * fac[n] % MOD) * finv[n - r]) % MOD;
}
mint nhr(long long n, long long r) { return com(n + r - 1, r); }
mint hom(long long n, long long r) { return com(n + r - 1, r); }
long long nhri(long long n, long long r) { return icom(n + r - 1, r); }
template <typename T>
T minv(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
T minv(T a) {
  if (a < mint_len) return inv[a];
  T u = 0, v = 1;
  T m = MOD;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T, typename U>
Modular<T> mpow(const Modular<T> &a, const U &b) {
  assert(b >= 0);
  long long x = a(), res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) (res *= x) %= MOD;
    (x *= x) %= MOD;
    p >>= 1;
  }
  return res;
}
template <typename T, typename U, typename V>
mint mpow(const T a, const U b, const V m = MOD) {
  assert(b >= 0);
  long long x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) (res *= x) %= m;
    (x *= x) %= m;
    p >>= 1;
  }
  return res;
}
template <typename T, typename U>
mint mpow(const T a, const U b) {
  assert(b >= 0);
  long long x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) (res *= x) %= MOD;
    (x *= x) %= MOD;
    p >>= 1;
  }
  return res;
}
template <typename T, typename U, typename V>
long long mpowi(const T &a, const U &b, const V &m = MOD) {
  assert(b >= 0);
  long long x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) (res *= x) %= m;
    (x *= x) %= m;
    p >>= 1;
  }
  return res;
}
template <typename T>
string to_string(const Modular<T> &number) {
  return to_string(number());
}
string yuri(const mint &a) {
  stringstream st;
  for (long long i = 0, _lim = 300; i < _lim; i++) {
    for (long long j = 0, _lim = 300; j < _lim; j++) {
      if ((mint)i / j == a) {
        st << i << " / " << j;
        return st.str();
      }
    }
  }
  for (long long i = 0, _lim = 1000; i < _lim; i++) {
    for (long long j = 0, _lim = 1000; j < _lim; j++) {
      if ((mint)i / j == a) {
        st << i << " / " << j;
        return st.str();
      }
    }
  }
  return st.str();
}
template <typename T>
std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
  stream << number();
  return stream;
}
template <typename T>
std::istream &operator>>(std::istream &stream, Modular<T> &number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
using PM = pair<mint, mint>;
using vm = vector<mint>;
using mapm = map<long long, mint>;
using umapm = unordered_map<long long, mint>;
struct setmod {
  setmod() {
    fac.resize(mint_len);
    finv.resize(mint_len);
    inv.resize(mint_len);
    inv[1] = fac[0] = finv[0] = 1;
    for (long long i = 2; i < mint_len; ++i)
      inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    for (long long i = 1; i < mint_len; ++i)
      fac[i] = fac[i - 1] * i % MOD, finv[i] = finv[i - 1] * inv[i] % MOD;
  }
} setmodv;
signed main() {
  long long x, n;
  cin >> x >> n;
  auto d = factorization(x);
  mint res = 1;
  for (auto &&p : d) {
    long long v = p;
    long long cou = 0;
    while (v <= n) {
      cou += n / v;
      if ((dou)v * p > numeric_limits<long long>::max()) break;
      v *= p;
    }
    res *= mpow(p, cou);
  }
  cout << res << endl;
  return 0;
}
