#include <bits/stdc++.h>
using namespace std;
static int LOCAL = 0;
const long long int mod = 1000000007ll;
const long long int MOD = 1000000009ll;
const long long int INF = LLONG_MAX / 10;
const int inf = INT_MAX / 2;
long long int count_bit(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
bool check_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  return (_mask & (x << _i)) == 0 ? false : true;
}
long long int set_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  _mask = _mask | (x << _i);
  return _mask;
}
long long int msb(long long int _mask) {
  long long int ret = -1;
  int cnt = 0;
  while (_mask) {
    if (_mask & 1) ret = cnt;
    _mask /= 2;
    cnt++;
  }
  return ret;
}
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  long long int x = a * b;
  x %= m;
  return x;
}
long long int gcd(long long int a, long long int b) {
  while (a && b) a > b ? a %= b : b %= a;
  return a + b;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
struct cmp {
  bool operator()(pair<int, int> const& l, pair<int, int> const& r) {
    if (l.first != r.first)
      return l.first > r.first;
    else
      return l.second > r.second;
  }
} myobject;
const int N = 1000100;
long long int fact[N], ifact[N], pf[N], po[N];
bool prime[N];
void sieve() {
  for (int i = 0; i <= N - 1; i++) {
    prime[i] = true;
    pf[i] = -1;
  }
  prime[0] = prime[1] = false;
  for (long long int i = 2; i < N; i++) {
    if (prime[i]) {
      pf[i] = i;
      for (long long int j = i * i; j < N; j += i) {
        prime[j] = false;
        pf[j] = i;
      }
    }
  }
}
long long int nCr(int n, int r) {
  long long int ret = fact[n];
  ret = mul(ret, mul(ifact[r], ifact[n - r]));
  return ret;
}
int main() {
  LOCAL = 0;
  if (LOCAL) {
    freopen("C:\\Users\\Smit Patel\\Downloads\\D-large.in", "r", stdin);
    freopen("C:\\Users\\Smit Patel\\Desktop\\out.txt", "w", stdout);
  }
  sieve();
  fact[0] = ifact[0] = po[0] = 1;
  for (int i = 1; i <= N - 1; i++) {
    fact[i] = mul(fact[i - 1], i);
    ifact[i] = powermod(fact[i], mod - 2);
    po[i] = mul(po[i - 1], 2);
  }
  int t, x, y;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &x, &y);
    long long int ans = po[y - 1];
    while (x > 1) {
      int z = pf[x], cnt = 0;
      while (x % z == 0) {
        x /= z;
        cnt++;
      }
      ans = mul(ans, nCr(y + cnt - 1, y - 1));
    }
    printf("%lld", ans);
    printf("\n");
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
static int LOCAL = 0;
const long long int mod = 1000000007ll;
const long long int MOD = 1000000009ll;
const long long int INF = LLONG_MAX / 10;
const int inf = INT_MAX / 2;
long long int count_bit(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
bool check_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  return (_mask & (x << _i)) == 0 ? false : true;
}
long long int set_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  _mask = _mask | (x << _i);
  return _mask;
}
long long int msb(long long int _mask) {
  long long int ret = -1;
  int cnt = 0;
  while (_mask) {
    if (_mask & 1) ret = cnt;
    _mask /= 2;
    cnt++;
  }
  return ret;
}
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  long long int x = a * b;
  x %= m;
  return x;
}
long long int gcd(long long int a, long long int b) {
  while (a && b) a > b ? a %= b : b %= a;
  return a + b;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
struct cmp {
  bool operator()(pair<int, int> const& l, pair<int, int> const& r) {
    if (l.first != r.first)
      return l.first > r.first;
    else
      return l.second > r.second;
  }
} myobject;
const int N = 1000100;
long long int fact[N], ifact[N], pf[N], po[N];
bool prime[N];
void sieve() {
  for (int i = 0; i <= N - 1; i++) {
    prime[i] = true;
    pf[i] = -1;
  }
  prime[0] = prime[1] = false;
  for (long long int i = 2; i < N; i++) {
    if (prime[i]) {
      pf[i] = i;
      for (long long int j = i * i; j < N; j += i) {
        prime[j] = false;
        pf[j] = i;
      }
    }
  }
}
long long int nCr(int n, int r) {
  long long int ret = fact[n];
  ret = mul(ret, mul(ifact[r], ifact[n - r]));
  return ret;
}
int main() {
  LOCAL = 0;
  if (LOCAL) {
    freopen("C:\\Users\\Smit Patel\\Downloads\\D-large.in", "r", stdin);
    freopen("C:\\Users\\Smit Patel\\Desktop\\out.txt", "w", stdout);
  }
  sieve();
  fact[0] = ifact[0] = po[0] = 1;
  for (int i = 1; i <= N - 1; i++) {
    fact[i] = mul(fact[i - 1], i);
    ifact[i] = powermod(fact[i], mod - 2);
    po[i] = mul(po[i - 1], 2);
  }
  int t, x, y;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &x, &y);
    long long int ans = po[y - 1];
    while (x > 1) {
      int z = pf[x], cnt = 0;
      while (x % z == 0) {
        x /= z;
        cnt++;
      }
      ans = mul(ans, nCr(y + cnt - 1, y - 1));
    }
    printf("%lld", ans);
    printf("\n");
  }
  return 0;
}

```