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; -  <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/3d08f4583882898cfb5a2c074c0b1c98e3c52a95.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
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 *A*<sub class="lower-index">*i*</sub> ≠ *B*<sub class="lower-index">*i*</sub>. Since the answer can be very large, print it modulo 10<sup class="upper-index">9</sup> + 7.
The first line contains one integer *q* (1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>) — the number of testcases to solve.

Then *q* lines follow, each containing two integers *x*<sub class="lower-index">*i*</sub> and *y*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>). Each of these lines represents a testcase.
In the second testcase of the example there are six *y*-factorizations:
 -  { - 4,  - 1}; -  { - 2,  - 2}; -  { - 1,  - 4}; -  {1, 4}; -  {2, 2}; -  {4, 1}.
2
6 3
4 2
36
6
1
524288 1000000
645043186
1
65536 1000000
928522471
1
5612 11399
215664246
mod = int(1e9 + 7)
M = int(1e5 + 5)
primes = []
is_prime = [1] * M
prime_facts = [[] for _ in range(M)]
for x in range(2, M):
    if is_prime[x]:
        primes.append(x)
        for y in range(x, M, x):
            prime_facts[y].append(x)
    for p in primes:
        if p * x >= M:
            break
        is_prime[p * x] = 0
        if x % p == 0:
            break


def power(base, exp, module):
    val = 1
    while exp:
        if exp & 1:
            val = val * base % module
        base = base * base % module
        exp >>= 1
    return val


N = 32
fc = [1] * N
iv = [1] * N
a = 1
for i in range(2, N):
    fc[i] = a = a * i % mod
iv[-1] = power(fc[-1], mod - 2, mod)
for i in range(N - 2, 1, -1):
    iv[i] = iv[i + 1] * (i + 1) % mod


# print(fc)
# print(iv)

def comb(n, m):
    # print(locals())
    return ((fc[n] * iv[m]) % mod) * iv[n - m] % mod


def f0(x, y):
    f2c = {}
    xx = x
    for p in prime_facts[x]:
        f2c[p] = 0
        while xx % p == 0:
            xx //= p
            f2c[p] += 1
    if xx > 1:
        f2c[xx] = 1
    ans = 1
    # print(x, y)
    for f, c in f2c.items():
        inc = comb(y + c - 1, c)
        # print(f, c, "|", inc)
        ans = ans * inc % mod
    base = ans
    for i in range(2, y + 1, 2):
        ans = (ans + base * comb(y, i) % mod) % mod
    return ans


q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    print(f0(x, y))
