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;  $\prod_{i = 1}^{y} F_{i} = x$. 

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_{i} ≠ B_{i}. Since the answer can be very large, print it modulo 10^9 + 7.


-----Input-----

The first line contains one integer q (1 ≤ q ≤ 10^5) — the number of testcases to solve.

Then q lines follow, each containing two integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^6). Each of these lines represents a testcase.


-----Output-----

Print q integers. i-th integer has to be equal to the number of y_{i}-factorizations of x_{i} modulo 10^9 + 7.


-----Example-----
Input
2
6 3
4 2

Output
36
6



-----Note-----

In the second testcase of the example there are six y-factorizations:  { - 4,  - 1};  { - 2,  - 2};  { - 1,  - 4};  {1, 4};  {2, 2};  {4, 1}.

Difficulty: interview

Starter code:

Solutions:
md = 10 ** 9 + 7

def cnk(n, k):
    if k > n//2:
        k = n - k
    ans = 1
    for i in range(n-k+1, n+1):
        ans *= i
    for i in range(2, k+1):
        ans //= i
    ans = ans % md
    return ans


def factor(n):
    pws = []
    dv = 2
    lp = 0
    while n % dv == 0:
        lp += 1
        n //= dv
    if lp:
        pws.append(lp)
    dv = 3
    while n > 1 and dv * dv <= n:
        lp = 0
        while n % dv == 0:
            lp += 1
            n //= dv
        if lp:
            pws.append(lp)
        dv += 2
    if n > 1:
        pws.append(1)
    return pws


def main():
    q = int(input())
    for __ in range(q):
        x, y = input().split()
        x, y = int(x), int(y)
        ans = pow(2, y - 1, md)
        for f in factor(x):
            cm = cnk(f + y - 1, y - 1)
            ans = (ans * cm) % md
        print(ans)


def __starting_point():
    main()
__starting_point()

md = 10 ** 9 + 7

def cnk(n, k):
    if k > n//2:
        k = n - k
    ans = 1
    for i in range(n-k+1, n+1):
        ans *= i
    for i in range(2, k+1):
        ans //= i
    ans = ans % md
    return ans


def factor(n):
    pws = []
    dv = 2
    lp = 0
    while n % dv == 0:
        lp += 1
        n //= dv
    if lp:
        pws.append(lp)
    dv = 3
    while n > 1 and dv * dv <= n:
        lp = 0
        while n % dv == 0:
            lp += 1
            n //= dv
        if lp:
            pws.append(lp)
        dv += 2
    if n > 1:
        pws.append(1)
    return pws


def main():
    q = int(input())
    for __ in range(q):
        x, y = input().split()
        x, y = int(x), int(y)
        ans = pow(2, y - 1, md)
        for f in factor(x):
            cm = cnk(f + y - 1, y - 1)
            ans = (ans * cm) % md
        print(ans)


def __starting_point():
    main()
__starting_point()

from array import array
md = 10 ** 9 + 7


def fact_all(N):
    lp = array('Q', [2]*(N+1))
    pr = array('Q', [2])
    pra = pr.append
    for i in range(3, N+1, 2):
        if lp[i] == 2:
            lp[i] = i
            pra(i)
        for p in pr:
            ip = i * p
            if p > lp[i] or ip > N:
                break
            lp[ip] = p
    return lp


def cnk(n, k):
    if k > n//2:
        k = n - k
    ans = 1
    for i in range(n-k+1, n+1):
        ans *= i
    for i in range(2, k+1):
        ans //= i
    ans = ans % md
    return ans


def factor(n, lpa=fact_all(10**6)):
    pws = []
    num_ones = 0
    dv = lpa[n]
    while n > 1 and dv * dv <= n:
        lp = 0
        c, o = divmod(n, dv)
        while o == 0:
            lp += 1
            n = c
            c, o = divmod(n, dv)
        if lp == 1:
            num_ones += 1
        else:
            pws.append(lp)
        dv = lpa[n]
    if n > 1:
        num_ones += 1
        # pws.append(1)
    return pws, num_ones


def main():
    q = int(input())
    for __ in range(q):
        x, y = input().split()
        x, y = int(x), int(y)
        ans = pow(2, y - 1, md)
        pws, num_ones = factor(x)
        for f in pws:
            cm = cnk(f + y - 1, f)
            ans = (ans * cm) % md
        if num_ones:
            ans = (ans * pow(y, num_ones, md)) % md
        print(ans)


def __starting_point():
    main()
__starting_point()

# from array import array
md = 10 ** 9 + 7


def fact_all(N):
    # lp = array('L', [2]*(N+1))
    # pr = array('L', [2])
    lp = [2]*(N+1)
    pr = [2]
    pra = pr.append
    for i in range(3, N+1, 2):
        if lp[i] == 2:
            lp[i] = i
            pra(i)
        for p in pr:
            ip = i * p
            if p > lp[i] or ip > N:
                break
            lp[ip] = p
    return lp


def cnk(n, k):
    if k > n//2:
        k = n - k
    ans = 1
    for i in range(n-k+1, n+1):
        ans *= i
    for i in range(2, k+1):
        ans //= i
    ans = ans % md
    return ans


def factor(n, lpa=fact_all(10**6)):
    pws = []
    num_ones = 0
    dv = lpa[n]
    while n > 1 and dv * dv <= n:
        lp = 0
        c, o = divmod(n, dv)
        while o == 0:
            lp += 1
            n = c
            c, o = divmod(n, dv)
        if lp == 1:
            num_ones += 1
        else:
            pws.append(lp)
        dv = lpa[n]
    if n > 1:
        num_ones += 1
        # pws.append(1)
    return pws, num_ones


def main():
    q = int(input())
    for __ in range(q):
        x, y = input().split()
        x, y = int(x), int(y)
        ans = pow(2, y - 1, md)
        pws, num_ones = factor(x)
        for f in pws:
            cm = cnk(f + y - 1, f)
            ans = (ans * cm) % md
        if num_ones:
            ans = (ans * pow(y, num_ones, md)) % md
        print(ans)


def __starting_point():
    main()
__starting_point()

from math import sqrt
from itertools import chain
import sys
input = sys.stdin.readline

mod = 10**9 + 7

ub = 1010
ub_sqrt = int(sqrt(ub))+1
primes = {2, 3} | set(chain(range(5, ub, 6), range(7, ub, 6)))
du = primes.difference_update
for n in chain(range(5, ub_sqrt, 6), range(7, ub_sqrt, 6)):
    if n in primes:
        du(range(n*3, ub, n*2))

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

q = int(input())
ans_a = [0]*q
for pi in range(q):
    x, y = map(int, input().split())
    ans = 1
    for p in primes:
        if x % p == 0:
            cnt = 0
            while x % p == 0:
                x //= p
                cnt += 1
            ans = ans * fac[cnt+y-1] * inv[cnt] * inv[y-1] % mod
    if x > 1:
        ans = ans * y % mod
    ans = ans * pow(2, y-1, mod) % mod
    ans_a[pi] = ans

print(*ans_a, sep='\n')