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
M=10**9+7
R=20+10**6
F=[1]*(R+1)
for i in range(2, R+1):
    F[i]=(F[i-1]*i)%M
def modpow(x, p):
    if p==0:
        return 1
    y=modpow(x, p//2)
    if p%2:
        return (y*y*x)%M
    return (y*y)%M
def modhyp(x):
    return modpow(x, M-2)
Fhyp=[1]*(R+1)
Fhyp[R]=modhyp(F[R])
for i in range(R-1, -1, -1):
    Fhyp[i]=(Fhyp[i+1]*(i+1))%M
def C(n, k):
    if k<0 or n<0:
        return 0
    if k>n:
        return 0
    return (F[n]*Fhyp[n-k]*Fhyp[k])%M
def pdd(x):
    d={}
    i=2
    while i*i<=x:
        if x%i==0:
            d[i]=0
            while x%i==0:
                x//=i
                d[i]+=1
        i+=1
    if x!=1:
        d[x]=1
    return d
for _ in range(int(input())):
    x,y=[int(e) for e in input().split()]
    d=pdd(x)
    ans=modpow(2, y-1)
    for e in d.values():
        ans=(ans*C(e+y-1, y-1))%M
    print(ans)