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
maxn=1000000
fac=[1]*(maxn+1)
inv=[1]*(maxn+1)
p=[list()]*(maxn+1)
mod=1000000007

def quick_pow(b,e):
    if(e==1):
        return b%mod
    else:
        if (e==0):
            return 1
        m=e//2
        v=quick_pow(b,m)
        if (m+m==e):
            return (v*v)%mod
        else:
            return (((v*v)%mod)*b)%mod

def count_prime(n,p):
    if (n%p==0):
        return count_prime(n//p,p)+1
    else:
        return 0

for i in range(2,maxn+1):
    fac[i]=(fac[i-1]*i)%mod
    inv[i]=(inv[i-1]*quick_pow(i,mod-2))%mod

for i in range(2,maxn+1):
    p[i]=list()

for i in range(2,maxn+1):
    if (len(p[i])==0):
        for j in range(i,maxn+1,i):
            p[j].append((i,count_prime(j,i)))

q=int(input())
for k in range(q):
    x_i, y_i = map(int,(input().split(" ")))

    result=1
    for pr,c in p[x_i]:
        up=c+y_i-1
        down1=c
        down2=y_i-1
        up=fac[up]
        down1=inv[down1]
        down2=inv[down2]
        r=(up*down1)%mod
        r*=down2
        r%=mod

        result*=r
        result%=mod

    print(result*(2<<(y_i-1)))
