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;
const long double PI = std::acos(-1.0L);
struct UInt {
  static const int BASE = (int)1e9;
  static const int WIDTH = 9;
  std::vector<int> digits;
  UInt(int64_t number = 0);
  UInt(const std::string& s);
  UInt(const std::vector<int>& digits);
  UInt& normalize();
  int compare(const UInt& other) const;
  UInt slow_mult(const UInt& other) const;
  UInt fast_mult(const UInt& other) const;
  UInt mult(const UInt& other) const;
  std::pair<UInt, UInt> div_mod(const UInt& other) const;
  UInt& operator+=(const int num);
  UInt& operator+=(const UInt& other);
  UInt& operator-=(const int num);
  UInt& operator-=(const UInt& other);
  UInt& operator*=(const int num);
  UInt& operator*=(const UInt& other);
  UInt& operator/=(const int num);
  UInt& operator/=(const UInt& other);
  UInt& operator%=(const UInt& other);
};
std::istream& operator>>(std::istream&, UInt&);
std::ostream& operator<<(std::ostream&, const UInt&);
UInt pow(UInt, int);
UInt gcd(UInt, UInt);
UInt operator+(const UInt&, const UInt&);
UInt operator-(const UInt&, const UInt&);
UInt operator*(const UInt&, const UInt&);
UInt operator/(const UInt&, const UInt&);
UInt operator%(const UInt&, const UInt&);
UInt operator+(const UInt&, const int);
UInt operator+(const int, const UInt&);
UInt operator-(const UInt&, const int);
UInt operator*(const UInt&, const int);
UInt operator*(const int, const UInt&);
UInt operator/(const UInt&, const int);
UInt operator^(const UInt&, const int);
bool operator<(const UInt&, const UInt&);
bool operator>(const UInt&, const UInt&);
bool operator<=(const UInt&, const UInt&);
bool operator>=(const UInt&, const UInt&);
bool operator==(const UInt&, const UInt&);
bool operator!=(const UInt&, const UInt&);
UInt& UInt::normalize() {
  while (digits.back() == 0 && (int)digits.size() > 1) digits.pop_back();
  for (auto d : digits) assert(0 <= d && d < BASE);
  return *this;
}
UInt::UInt(int64_t number) {
  assert(number >= 0);
  do {
    digits.push_back(number % BASE);
    number /= BASE;
  } while (number > 0);
  normalize();
}
UInt::UInt(const std::vector<int>& digits) : digits(digits) { normalize(); }
UInt::UInt(const std::string& s) {
  const int size = (int)s.size();
  for (int idGroup = 1, nGroups = size / WIDTH; idGroup <= nGroups; ++idGroup) {
    digits.push_back(std::stoi(s.substr(size - idGroup * WIDTH, WIDTH)));
  }
  if (size % WIDTH != 0) {
    digits.push_back(std::stoi(s.substr(0, size % WIDTH)));
  }
  normalize();
}
UInt& UInt::operator+=(const int num) {
  assert(num >= 0);
  if (num >= BASE) {
    return *this += UInt(num);
  }
  int rem = num;
  for (int i = 0; rem > 0; ++i) {
    if (i >= (int)digits.size()) digits.push_back(0);
    rem += digits[i];
    if (rem >= BASE) {
      digits[i] = rem - BASE;
      rem = 1;
    } else {
      digits[i] = rem;
      rem = 0;
    }
  }
  return this->normalize();
}
UInt& UInt::operator+=(const UInt& other) {
  if (other.digits.size() == 1u) {
    return *this += other.digits[0];
  }
  const int s1 = this->digits.size();
  const int s2 = other.digits.size();
  int rem = 0;
  for (int i = 0; i < s1 || i < s2 || rem > 0; ++i) {
    int d1 = i < s1 ? this->digits[i] : (digits.push_back(0), 0);
    int d2 = i < s2 ? other.digits[i] : 0;
    rem += d1 + d2;
    auto div = rem / BASE;
    digits[i] = rem - div * BASE;
    rem = div;
  }
  return this->normalize();
}
UInt& UInt::operator-=(const int num) {
  assert(num >= 0);
  if (num >= BASE) {
    return *this -= UInt(num);
  }
  int rem = -num;
  for (int i = 0; i < (int)digits.size() && rem < 0; ++i) {
    rem += digits[i];
    if (rem < 0) {
      digits[i] = rem + BASE;
      rem = -1;
    } else {
      digits[i] = rem;
      rem = 0;
    }
  }
  assert(rem == 0);
  return this->normalize();
}
UInt& UInt::operator-=(const UInt& other) {
  if (other.digits.size() == 1u) {
    return *this -= other.digits[0];
  }
  const int s1 = this->digits.size();
  const int s2 = other.digits.size();
  assert(s1 >= s2);
  int rem = 0;
  for (int i = 0; i < s1; ++i) {
    int d2 = i < s2 ? other.digits[i] : 0;
    rem += this->digits[i] - d2;
    if (rem < 0) {
      digits[i] = rem + BASE;
      rem = -1;
    } else {
      digits[i] = rem;
      rem = 0;
      if (i >= s2) break;
    }
  }
  assert(rem == 0);
  return this->normalize();
}
UInt& UInt::operator*=(const int num) {
  assert(num >= 0);
  if (num >= BASE) {
    return *this *= UInt(num);
  }
  int64_t rem = 0;
  for (auto& d : digits) {
    rem += 1LL * d * num;
    auto div = rem / BASE;
    d = rem - div * BASE;
    rem = div;
  }
  if (rem > 0) digits.push_back(rem);
  return this->normalize();
}
UInt UInt::slow_mult(const UInt& other) const {
  if (other.digits.size() == 1u) {
    return *this * other.digits[0];
  }
  const int s1 = (int)this->digits.size();
  const int s2 = (int)other.digits.size();
  std::vector<int> temp(s1 + s2);
  for (int i = 0; i < s1; ++i) {
    int64_t rem = 0;
    for (int j = 0; j < s2; ++j) {
      rem += temp[i + j] + 1LL * this->digits[i] * other.digits[j];
      auto div = rem / BASE;
      temp[i + j] = rem - div * BASE;
      rem = div;
    }
    if (rem > 0) temp[i + s2] += rem;
  }
  return UInt(temp);
}
UInt UInt::fast_mult(const UInt& other) const {
  if (other.digits.size() == 1u) {
    return *this * other.digits[0];
  }
  std::function<int(int, int)> reverse = [](int number, int nBits) {
    int res = 0;
    for (int i = 0; i < nBits; ++i) {
      if (number & (1 << i)) {
        res |= 1 << (nBits - 1 - i);
      }
    }
    return res;
  };
  std::function<void(std::vector<std::complex<long double> >&, bool)> fft =
      [&reverse](std::vector<std::complex<long double> >& a, bool invert) {
        const int n = (int)a.size();
        int nBits = 0;
        while ((1 << nBits) < n) ++nBits;
        for (int i = 0; i < n; ++i) {
          if (i < reverse(i, nBits)) {
            std::swap(a[i], a[reverse(i, nBits)]);
          }
        }
        for (int len = 2; len <= n; len <<= 1) {
          auto ang = 2 * PI / len * (invert ? -1 : 1);
          std::complex<long double> wlen(std::cos(ang), std::sin(ang));
          for (int i = 0; i < n; i += len) {
            std::complex<long double> w(1);
            for (int j = 0; j < len / 2; ++j) {
              std::complex<long double> u = a[i + j];
              std::complex<long double> v = a[i + j + len / 2] * w;
              a[i + j] = u + v;
              a[i + j + len / 2] = u - v;
              w *= wlen;
            }
          }
        }
        if (invert) {
          for (int i = 0; i < n; ++i) {
            a[i] /= n;
          }
        }
      };
  assert(BASE == 1000 * 1000 * 1000);
  std::function<std::vector<std::complex<long double> >(const UInt&)> prepare =
      [](const UInt& number) {
        std::vector<std::complex<long double> > result;
        result.reserve(3 * number.digits.size());
        for (auto d : number.digits) {
          result.push_back(d % 1000);
          result.push_back(d / 1000 % 1000);
          result.push_back(d / 1000000);
        }
        return result;
      };
  auto fa = prepare(*this);
  auto fb = prepare(other);
  int n = 1;
  while (n < (int)std::max(fa.size(), fb.size())) n *= 2;
  n *= 2;
  fa.resize(n);
  fb.resize(n);
  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < n; ++i) {
    fa[i] *= fb[i];
  }
  fft(fa, true);
  std::vector<int64_t> temp(n);
  for (int i = 0; i < (int)fa.size(); ++i) {
    temp[i] = int64_t(fa[i].real() + 0.5);
  }
  int64_t carry = 0;
  for (int i = 0; i < n || carry > 0; ++i) {
    if (i >= n) temp.push_back(0);
    temp[i] += carry;
    carry = temp[i] / 1000;
    temp[i] -= carry * 1000;
    assert(temp[i] >= 0);
  }
  std::vector<int> res;
  res.reserve(this->digits.size() + other.digits.size());
  for (int i = 0; i < n; i += 3) {
    int c = temp[i];
    int b = i + 1 < n ? temp[i + 1] : 0;
    int a = i + 2 < n ? temp[i + 2] : 0;
    res.push_back(c + 1000 * (b + 1000 * a));
  }
  return UInt(res);
}
UInt UInt::mult(const UInt& other) const {
  int len1 = (int)this->digits.size();
  int len2 = (int)other.digits.size();
  int temp = 3 * std::max(len1, len2);
  int pow = 1;
  while (pow < temp) pow *= 2;
  pow *= 2;
  int op1 = len1 * len2;
  int op2 = 3 * pow * std::log(pow) / std::log(2);
  return op1 >= 15 * op2 ? fast_mult(other) : slow_mult(other);
}
UInt& UInt::operator/=(const int num) {
  assert(num > 0);
  if (num >= BASE) {
    return *this /= UInt(num);
  }
  int64_t rem = 0;
  for (int j = (int)digits.size() - 1; j >= 0; --j) {
    (rem *= BASE) += digits[j];
    auto div = rem / num;
    digits[j] = div;
    rem -= div * num;
  }
  return this->normalize();
}
int operator%(const UInt& a, const int num) {
  assert(num > 0);
  int64_t rem = 0;
  for (int i = (int)a.digits.size() - 1; i >= 0; --i) {
    ((rem *= UInt::BASE) += a.digits[i]) %= num;
  }
  return rem;
}
std::pair<UInt, UInt> UInt::div_mod(const UInt& other) const {
  if (other.digits.size() == 1u) {
    return {std::move(*this / other.digits[0]), *this % other.digits[0]};
  }
  const int norm = BASE / (other.digits.back() + 1);
  const UInt a = *this * norm;
  const UInt b = other * norm;
  const int a_size = (int)a.digits.size();
  const int b_size = (int)b.digits.size();
  UInt q, r;
  q.digits.resize(a_size);
  for (int i = a_size - 1; i >= 0; --i) {
    r *= BASE;
    r += a.digits[i];
    int s1 = (int)r.digits.size() <= b_size ? 0 : r.digits[b_size];
    int s2 = (int)r.digits.size() <= b_size - 1 ? 0 : r.digits[b_size - 1];
    int d = (1LL * BASE * s1 + s2) / b.digits.back();
    auto temp = b * d;
    while (r < temp) {
      r += b;
      --d;
    }
    r -= temp;
    q.digits[i] = d;
  }
  return {std::move(q.normalize()), std::move(r /= norm)};
}
int UInt::compare(const UInt& other) const {
  if (this->digits.size() > other.digits.size()) return 1;
  if (this->digits.size() < other.digits.size()) return -1;
  for (int i = (int)digits.size() - 1; i >= 0; --i) {
    if (this->digits[i] > other.digits[i]) return 1;
    if (this->digits[i] < other.digits[i]) return -1;
  }
  return 0;
}
bool operator<(const UInt& a, const UInt& b) { return a.compare(b) < 0; }
bool operator>(const UInt& a, const UInt& b) { return a.compare(b) > 0; }
bool operator==(const UInt& a, const UInt& b) { return a.compare(b) == 0; }
bool operator<=(const UInt& a, const UInt& b) { return a.compare(b) <= 0; }
bool operator>=(const UInt& a, const UInt& b) { return a.compare(b) >= 0; }
bool operator!=(const UInt& a, const UInt& b) { return a.compare(b) != 0; }
std::istream& operator>>(std::istream& is, UInt& number) {
  std::string s;
  is >> s;
  number = UInt(s);
  return is;
}
std::ostream& operator<<(std::ostream& os, const UInt& number) {
  os << number.digits.back();
  for (int i = (int)number.digits.size() - 2; i >= 0; --i) {
    os << std::setw(UInt::WIDTH) << std::setfill('0') << number.digits[i];
  }
  return os << std::setfill(' ');
}
UInt operator+(const UInt& a, const UInt& b) { return UInt(a) += b; }
UInt operator-(const UInt& a, const UInt& b) { return UInt(a) -= b; }
UInt operator*(const UInt& a, const UInt& b) { return a.mult(b); }
UInt operator/(const UInt& a, const UInt& b) { return a.div_mod(b).first; }
UInt operator%(const UInt& a, const UInt& b) { return a.div_mod(b).second; }
UInt& UInt::operator*=(const UInt& other) { return *this = *this * other; }
UInt& UInt::operator/=(const UInt& other) { return *this = *this / other; }
UInt& UInt::operator%=(const UInt& other) { return *this = *this % other; }
UInt operator+(const UInt& a, const int b) { return UInt(a) += b; }
UInt operator+(const int a, const UInt& b) { return b * a; }
UInt operator-(const UInt& a, const int b) { return UInt(a) -= b; }
UInt operator*(const UInt& a, const int b) { return UInt(a) *= b; }
UInt operator*(const int a, const UInt& b) { return b * a; }
UInt operator/(const UInt& a, const int b) { return UInt(a) /= b; }
UInt operator^(const UInt& a, const int n) { return pow(a, n); }
UInt pow(UInt a, int n) {
  UInt res = 1;
  while (n > 0) {
    if (n % 2 != 0) res *= a;
    a *= a;
    n /= 2;
  }
  return res;
}
UInt gcd(UInt a, UInt b) {
  while (b != 0) {
    auto rem = a % b;
    a = b;
    b = rem;
  }
  return a;
}
UInt mod = 1e9 + 7;
UInt fastPow(UInt N, UInt N2) {
  if (N2 == 0) return 1;
  if (N2 == 1) return N;
  UInt tmp = fastPow(N, N2 / 2);
  tmp *= tmp;
  tmp = tmp % mod;
  if (N2 % 2 == 1) tmp *= N;
  tmp = tmp % mod;
  return tmp;
}
vector<UInt> primes;
int main() {
  UInt x, n;
  cin >> x >> n;
  vector<bool> isPrime(1e6, true);
  for (int c = 2; c < isPrime.size(); c++) {
    if (!isPrime[c]) continue;
    primes.push_back(UInt(c));
    for (int c2 = c; c2 < isPrime.size(); c2 += c) isPrime[c2] = false;
  }
  UInt res = 1;
  for (int c = 0;
       c < primes.size() && primes[c] * primes[c] <= x && primes[c] <= n; c++) {
    if (x % primes[c] != 0) continue;
    UInt maxPow = primes[c];
    UInt tmpSub = 0;
    while (maxPow * primes[c] <= n) {
      maxPow *= primes[c];
    }
    while (maxPow != 0) {
      UInt tmpAct = n / maxPow;
      tmpAct -= tmpSub;
      res *= fastPow(maxPow, tmpAct) % mod;
      res = res % mod;
      tmpSub += tmpAct;
      maxPow /= primes[c];
    }
    res = res % mod;
    while (x % primes[c] == 0) x /= primes[c];
  }
  if (x != 1) {
    UInt p = x;
    UInt maxPow = p;
    UInt tmpSub = 0;
    while (maxPow * p <= n) {
      maxPow *= p;
    }
    while (maxPow != 0) {
      UInt tmpAct = n / maxPow;
      tmpAct -= tmpSub;
      res *= fastPow(maxPow, tmpAct) % mod;
      tmpSub += tmpAct;
      maxPow /= p;
      res = res % mod;
    }
    res = res % mod;
  }
  cout << res << endl;
}
