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
R,G=lambda:map(int,input().split()),range;t,=R();M=10**9+7;n=2*10**6+1
g=[1,1]+[0]*(n-1)
for i in G(2,n+1):g[i]=g[i-1]*i%M
for _ in G(t):
  x,y=R();y-=1;z=pow(2,y,M)
  for f in G(2,int(abs(x)**0.5)+1):
    c=0
    while x%f==0:c+=1;x//=f
    if c:z*=g[c+y]*pow(g[c]*g[y]%M,M-2,M)%M;z%=M
  if x>1:z=z*(y+1)%M
  print(z)