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
import sys

mod = 10**9 + 7
max_n = 10**6 + 100
fac, inv = [1]*max_n, [1]*max_n
for i in range(2, max_n):
    fac[i] = fac[i-1] * i % mod
inv[-1] = pow(fac[-1], mod-2, mod)
for i in range(max_n-1, 0, -1):
    inv[i-1] = inv[i] * i % mod


def get_primes(n: int):
    from itertools import chain
    from array import array
    primes = [2, 3]
    is_prime = (array('b', (0, 0, 1, 1, 0, 1, 0)) +
                array('b', (1, 0, 0, 0, 1, 0))*((n-1)//6))

    for i in chain.from_iterable((range(5, n+1, 6), range(7, n+1, 6))):
        if is_prime[i]:
            primes.append(i)
            for j in range(i*3, n+1, i*2):
                is_prime[j] = 0

    return is_prime, primes


_, primes = get_primes(10**3)
q = int(sys.stdin.buffer.readline().decode('utf-8'))
ans = [0]*q
for i in range(q):
    x, y = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
    pfac = []
    for p in primes:
        if x % p == 0:
            pfac.append(0)
            while x % p == 0:
                pfac[-1] += 1
                x //= p
    if x > 1:
        pfac.append(1)

    res = 1
    for c in pfac:
        res = (res * fac[c+y-1] * inv[y-1] * inv[c]) % mod
    res = res * pow(2, y-1, mod) % mod
    ans[i] = res

sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))
