#include <bits/stdc++.h>
using namespace std;
char *p1, *p2;
char buffer[2000005];
template <class T>
void read(T& x) {
  char ch = ((p1 == p2 &&
              (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
                 ? EOF
                 : *p1++);
  x = 0;
  bool f = 1;
  while (!('0' <= ch && ch <= '9') && ch != '-')
    ch = ((p1 == p2 &&
           (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
              ? EOF
              : *p1++);
  if (ch == '-')
    f = 0,
    ch = ((p1 == p2 &&
           (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
              ? EOF
              : *p1++);
  while ('0' <= ch && ch <= '9')
    x = (x << 1) + (x << 3) + ch - '0',
    ch = ((p1 == p2 &&
           (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
              ? EOF
              : *p1++);
  if (!f) x = -x;
}
int n, m;
int p[2000005];
bool vis[2000005];
int nex[2000005];
int cnt = 0;
void init() {
  for (register int i = 2; i <= 2000005 - 1; i++) {
    if (!vis[i]) p[++cnt] = i, nex[i] = cnt;
    for (register int j = 1; j <= cnt; j++) {
      if (i * p[j] >= 2000005) break;
      vis[i * p[j]] = 1;
      nex[i * p[j]] = j;
      if (i % p[j] == 0) break;
    }
  }
}
long long int fac[2000005];
long long int ifac[2000005];
long long int inv[2000005];
long long int two[2000005];
void get_com() {
  fac[0] = ifac[0] = inv[1] = two[0] = 1;
  for (register int i = 1; i <= 2000005 - 1; i++)
    two[i] = (two[i - 1] << 1) % 1000000007;
  for (register int i = 1; i <= 2000005 - 1; i++)
    fac[i] = fac[i - 1] * i % 1000000007;
  for (register int i = 2; i <= 2000005 - 1; i++)
    inv[i] = 1000000007 - 1000000007 / i * inv[1000000007 % i] % 1000000007;
  for (register int i = 1; i <= 2000005 - 1; i++)
    ifac[i] = ifac[i - 1] * inv[i] % 1000000007;
}
long long int cal(int m, int n) {
  if (m < n) return 0;
  return fac[m] * ifac[n] % 1000000007 * ifac[m - n] % 1000000007;
}
void work(int x, int y) {
  long long int ans = two[y - 1];
  while (x > 1) {
    int d = nex[x];
    int ct = 0;
    while (nex[x] == d) ct++, x /= p[nex[x]];
    ans = ans * cal(ct + y - 1, y - 1) % 1000000007;
  }
  printf("%I64d\n", ans);
}
int main() {
  init(), get_com();
  int x, y;
  read(m);
  for (register int i = 1; i <= m; i++) {
    read(x), read(y);
    work(x, y);
  }
  return 0;
}

### Prompt

Please formulate a cpp solution 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;
char *p1, *p2;
char buffer[2000005];
template <class T>
void read(T& x) {
  char ch = ((p1 == p2 &&
              (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
                 ? EOF
                 : *p1++);
  x = 0;
  bool f = 1;
  while (!('0' <= ch && ch <= '9') && ch != '-')
    ch = ((p1 == p2 &&
           (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
              ? EOF
              : *p1++);
  if (ch == '-')
    f = 0,
    ch = ((p1 == p2 &&
           (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
              ? EOF
              : *p1++);
  while ('0' <= ch && ch <= '9')
    x = (x << 1) + (x << 3) + ch - '0',
    ch = ((p1 == p2 &&
           (p2 = (p1 = buffer) + fread(buffer, 1, 2000005, stdin), p1 == p2))
              ? EOF
              : *p1++);
  if (!f) x = -x;
}
int n, m;
int p[2000005];
bool vis[2000005];
int nex[2000005];
int cnt = 0;
void init() {
  for (register int i = 2; i <= 2000005 - 1; i++) {
    if (!vis[i]) p[++cnt] = i, nex[i] = cnt;
    for (register int j = 1; j <= cnt; j++) {
      if (i * p[j] >= 2000005) break;
      vis[i * p[j]] = 1;
      nex[i * p[j]] = j;
      if (i % p[j] == 0) break;
    }
  }
}
long long int fac[2000005];
long long int ifac[2000005];
long long int inv[2000005];
long long int two[2000005];
void get_com() {
  fac[0] = ifac[0] = inv[1] = two[0] = 1;
  for (register int i = 1; i <= 2000005 - 1; i++)
    two[i] = (two[i - 1] << 1) % 1000000007;
  for (register int i = 1; i <= 2000005 - 1; i++)
    fac[i] = fac[i - 1] * i % 1000000007;
  for (register int i = 2; i <= 2000005 - 1; i++)
    inv[i] = 1000000007 - 1000000007 / i * inv[1000000007 % i] % 1000000007;
  for (register int i = 1; i <= 2000005 - 1; i++)
    ifac[i] = ifac[i - 1] * inv[i] % 1000000007;
}
long long int cal(int m, int n) {
  if (m < n) return 0;
  return fac[m] * ifac[n] % 1000000007 * ifac[m - n] % 1000000007;
}
void work(int x, int y) {
  long long int ans = two[y - 1];
  while (x > 1) {
    int d = nex[x];
    int ct = 0;
    while (nex[x] == d) ct++, x /= p[nex[x]];
    ans = ans * cal(ct + y - 1, y - 1) % 1000000007;
  }
  printf("%I64d\n", ans);
}
int main() {
  init(), get_com();
  int x, y;
  read(m);
  for (register int i = 1; i <= m; i++) {
    read(x), read(y);
    work(x, y);
  }
  return 0;
}

```