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 = 1e9+7;
from functools import lru_cache

def modexp(a, n):
	ans = 1
	while (n):
		if (n&1):
		    ans = (ans*a)%mod
		a = (a*a)%mod
		n = n>>1
	return ans

@lru_cache(100000)
def rec(x, y):
	if (y==0):
	    return 0
	if (y==1):
	    return 1

	# calculate factors O(sqrt(n))
	ans = 0
	f1 = 1
	while (f1*f1 <= x):
		if (x%f1==0):
			ans = (ans + rec(x/f1, y-1))%mod

			f2 = x/f1
			if (f2!=f1):
			    ans = (ans + rec(x/f2, y-1))%mod
		f1 += 1

	return ans

for i in range(int(input())):
    x,y = list(map(int, input().split(' ')))
    print(int((rec(x,y) * modexp(2, y-1))%mod))
