#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const int mod = 1e9 + 7;
const int MXI = 1e9 + 5;
const long long MXL = 1e18 + 5;
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long lcm(long long a, long long b) { return (a / gcd(a, b) * b); }
long long bigmod(long long a, long long p, long long M) {
  p %= (M - 1);
  long long result = 1LL;
  while (p > 0LL) {
    if (p & 1LL) result = result * a % M;
    a = a * a % M;
    p >>= 1LL;
  }
  return result;
}
long long inverse(long long a, long long M) {
  if (gcd(a, M) == 1) return bigmod(a, M - 2, M) % M;
  return 1;
}
long long ncr(long long a, long long b) {
  long long x = max(a - b, b), ans = 1;
  for (long long K = a, L = 1; K >= x + 1; K--, L++) {
    ans = ans * K % mod;
    ans = ans * inverse(L, mod) % mod;
  }
  return ans;
}
long long egcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = egcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
void pbin(int n) {
  vector<int> vv;
  while (n) {
    vv.push_back(n % 2);
    n >>= 1;
  }
  for (int K = (int)vv.size(); K <= 5; K++) vv.push_back(0);
  reverse(begin(vv), end(vv));
  for (auto x : vv) cout << x;
  cout << "\n";
}
const int MX = 1e6;
vector<int> primes;
vector<bool> mark(1000002);
void sieve(int n) {
  int i, j, limit = sqrt(n * 1.) + 2;
  mark[1] = 1;
  for (i = 4; i <= n; i += 2) mark[i] = 1;
  primes.push_back(2);
  for (i = 3; i <= n; i += 2) {
    if (!mark[i]) {
      primes.push_back(i);
      if (i <= limit) {
        for (j = i * i; j <= n; j += i * 2) {
          mark[j] = 1;
        }
      }
    }
  }
}
long long divs(long long n, int y) {
  long long cnt, i, ans = 1;
  for (i = 0; i < (int)primes.size() && ((long long)primes[i] * primes[i]) <= n;
       i++) {
    if (n % primes[i] == 0) {
      cnt = 0;
      while (n % primes[i] == 0) {
        n /= primes[i];
        cnt++;
      }
      ans = ans * ncr(y + cnt - 1, cnt) % mod;
    }
  }
  if (n > 1) {
    ans = ans * y % mod;
  }
  return ans;
}
long long fact[MX + 5];
void task() {
  long long t, x, y;
  sieve(1005);
  fact[0] = 1;
  fact[1] = 2;
  for (long long K = 2; K <= MX; K++) fact[K] = fact[K - 1] * 2 % mod;
  cin >> t;
  while (t--) {
    cin >> x >> y;
    long long ans = 0;
    ans = divs(x, y);
    ans = ans * fact[y - 1] % mod;
    cout << ans << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  task();
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

You are given two positive integer numbers x and y. An array F is called an y-factorization of x iff the following conditions are met:

  * There are y elements in F, and all of them are integer numbers; 
  * <image>. 



You have to count the number of pairwise distinct arrays that are y-factorizations of x. Two arrays A and B are considered different iff there exists at least one index i (1 ≤ i ≤ y) such that Ai ≠ Bi. Since the answer can be very large, print it modulo 109 + 7.

Input

The first line contains one integer q (1 ≤ q ≤ 105) — the number of testcases to solve.

Then q lines follow, each containing two integers xi and yi (1 ≤ xi, yi ≤ 106). Each of these lines represents a testcase.

Output

Print q integers. i-th integer has to be equal to the number of yi-factorizations of xi modulo 109 + 7.

Example

Input

2
6 3
4 2


Output

36
6

Note

In the second testcase of the example there are six y-factorizations:

  * { - 4, - 1}; 
  * { - 2, - 2}; 
  * { - 1, - 4}; 
  * {1, 4}; 
  * {2, 2}; 
  * {4, 1}. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const int mod = 1e9 + 7;
const int MXI = 1e9 + 5;
const long long MXL = 1e18 + 5;
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long lcm(long long a, long long b) { return (a / gcd(a, b) * b); }
long long bigmod(long long a, long long p, long long M) {
  p %= (M - 1);
  long long result = 1LL;
  while (p > 0LL) {
    if (p & 1LL) result = result * a % M;
    a = a * a % M;
    p >>= 1LL;
  }
  return result;
}
long long inverse(long long a, long long M) {
  if (gcd(a, M) == 1) return bigmod(a, M - 2, M) % M;
  return 1;
}
long long ncr(long long a, long long b) {
  long long x = max(a - b, b), ans = 1;
  for (long long K = a, L = 1; K >= x + 1; K--, L++) {
    ans = ans * K % mod;
    ans = ans * inverse(L, mod) % mod;
  }
  return ans;
}
long long egcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = egcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
void pbin(int n) {
  vector<int> vv;
  while (n) {
    vv.push_back(n % 2);
    n >>= 1;
  }
  for (int K = (int)vv.size(); K <= 5; K++) vv.push_back(0);
  reverse(begin(vv), end(vv));
  for (auto x : vv) cout << x;
  cout << "\n";
}
const int MX = 1e6;
vector<int> primes;
vector<bool> mark(1000002);
void sieve(int n) {
  int i, j, limit = sqrt(n * 1.) + 2;
  mark[1] = 1;
  for (i = 4; i <= n; i += 2) mark[i] = 1;
  primes.push_back(2);
  for (i = 3; i <= n; i += 2) {
    if (!mark[i]) {
      primes.push_back(i);
      if (i <= limit) {
        for (j = i * i; j <= n; j += i * 2) {
          mark[j] = 1;
        }
      }
    }
  }
}
long long divs(long long n, int y) {
  long long cnt, i, ans = 1;
  for (i = 0; i < (int)primes.size() && ((long long)primes[i] * primes[i]) <= n;
       i++) {
    if (n % primes[i] == 0) {
      cnt = 0;
      while (n % primes[i] == 0) {
        n /= primes[i];
        cnt++;
      }
      ans = ans * ncr(y + cnt - 1, cnt) % mod;
    }
  }
  if (n > 1) {
    ans = ans * y % mod;
  }
  return ans;
}
long long fact[MX + 5];
void task() {
  long long t, x, y;
  sieve(1005);
  fact[0] = 1;
  fact[1] = 2;
  for (long long K = 2; K <= MX; K++) fact[K] = fact[K - 1] * 2 % mod;
  cin >> t;
  while (t--) {
    cin >> x >> y;
    long long ans = 0;
    ans = divs(x, y);
    ans = ans * fact[y - 1] % mod;
    cout << ans << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  task();
  return 0;
}

```