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;
long long compute_hash(string const &s, bool small) {
  int p;
  if (small)
    p = 31;
  else
    p = 53;
  const int m = 1e9 + 9;
  long long hash_value = 0;
  long long p_pow = 1;
  for (char c : s) {
    hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
    p_pow = (p_pow * p) % m;
  }
  return hash_value;
}
vector<vector<int>> group_identical_strings(vector<string> const &s,
                                            bool small) {
  int n = s.size();
  vector<pair<long long, int>> hashes(n);
  for (int i = 0; i < n; i++) hashes[i] = {compute_hash(s[i], small), i};
  sort(hashes.begin(), hashes.end());
  vector<vector<int>> groups;
  for (int i = 0; i < n; i++) {
    if (i == 0 || hashes[i].first != hashes[i - 1].first) groups.emplace_back();
    groups.back().push_back(hashes[i].second);
  }
  return groups;
}
template <typename T>
struct min_queue {
  deque<T> q;
  T get_min() { return q.front(); }
  void add(T element) {
    while (!q.empty() && q.back() > element) q.pop_back();
    q.push_back(element);
  }
  void remove(T element) {
    if (!q.empty() && q.front() == element) q.pop_front();
  }
};
template <typename T>
struct min_queue_3 {
  stack<pair<T, T>> s1, s2;
  T get_min() {
    if (s1.empty() || s2.empty())
      return s1.empty() ? s2.top().second : s1.top().second;
    return min(s1.top().second, s2.top().second);
  }
  void add(T new_element) {
    T minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
    s1.push({new_element, minimum});
  }
  void remove() {
    if (s2.empty()) {
      while (!s1.empty()) {
        T element = s1.top().first;
        s1.pop();
        T minimum = s2.empty() ? element : min(element, s2.top().second);
        s2.push({element, minimum});
      }
    }
    int remove_element = s2.top().first;
    s2.pop();
  }
};
template <typename T>
struct segment_tree_max {
  vector<T> t;
  explicit segment_tree_max(T n) { t.resize(4 * n); }
  void build(vector<T> a, T v, T tl, T tr) {
    if (tl == tr) {
      t[v] = a[tl];
    } else {
      T tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
  }
  pair<T, T> _max(T v, T tl, T tr, T l, T r) {
    if (l > r) return make_pair(INT_MIN, -1);
    if (l == tl && r == tr) {
      return make_pair(t[v], r);
    }
    T tm = (tl + tr) / 2;
    auto I1 = _max(v * 2, tl, tm, l, min(r, tm));
    auto I2 = _max(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
    if (I1.first > I2.first) return I1;
    return I2;
  }
  void update(T v, T tl, T tr, T pos, T new_val) {
    if (tl == tr) {
      t[v] = new_val;
    } else {
      T tm = (tl + tr) / 2;
      if (pos <= tm)
        update(v * 2, tl, tm, pos, new_val);
      else
        update(v * 2 + 1, tm + 1, tr, pos, new_val);
      t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
  }
};
template <typename T>
T nCr(T n, T k) {
  T res = 1;
  if (k > (n - k)) k = n - k;
  for (int i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
template <typename T>
vector<T> prefix_function(const string &s) {
  vector<T> pi(s.length());
  for (T i = 1; i < (T)s.length(); i++) {
    T j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
const int trie_alphabet_size = 26;
template <typename T>
struct trie_node {
  unordered_map<T, T> next;
  bool leaf = false;
};
vector<trie_node<int>> trie(1);
void add_string(string const &s) {
  int v = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (trie[v].next.find(c) == trie[v].next.end()) {
      trie[v].next[c] = trie.size();
      trie.emplace_back();
    }
    v = trie[v].next[c];
  }
  trie[v].leaf = true;
}
vector<int> primeFactors(int n) {
  vector<int> ans;
  if (n % 2 == 0) ans.push_back(2);
  while (n % 2 == 0) {
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    if (n % i == 0) ans.push_back(i);
    while (n % i == 0) {
      n = n / i;
    }
  }
  if (n > 2) ans.push_back(n);
  return ans;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long x, n;
  cin >> x >> n;
  vector<int> p = primeFactors(x);
  long long ans = 1;
  for (auto i : p) {
    long long pwr = i;
    long long a = 0;
    long long k = n;
    while (true) {
      if (k == 0) break;
      a += (k / pwr);
      k /= pwr;
    }
    ans = ((ans * power(i, a, 1000000007)) % 1000000007);
  }
  cout << ans;
  return 0;
}
