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
import heapq;
import math;
from collections import Counter, deque;
from itertools import permutations
import random;
import sys;
from os import path;

from random import getrandbits;

mod = 10**9 + 7;

# sys.stdin = open('sieve.in', 'r');








powers = [];
factorials = [1];
currMul = 1;

for i in range(1, 3 * 10**6):
    currMul *= i;
    currMul %= mod;
    factorials.append(currMul);





N = 10**6 + 5;

def nCr(n, r):
    numerator = factorials[n];
    denominator = factorials[n - r] * factorials[r];
    denominator %= mod;
    return (numerator * pow(denominator, mod - 2, mod)) % mod





spf = [0 for i in range(N)];

def sieve():
    for i in range(2, N):
        if not spf[i]:
            for j in range(i, N, i):
                if not spf[j]: spf[j] = i;







sieve();


powers.append(1);

currMul = 1;
for i in range(N):
    currMul *= 2;
    currMul %= mod;
    powers.append(currMul);

t = int(input())


for _ in range(t):
    x, y = map(int, input().split())



    def solve():


        cnts = [];

        currNum = x;

        while currNum != 1:
            cnt = 0;
            currSpf = spf[currNum];
            while (currNum % currSpf) == 0:
                currNum //= currSpf
                cnt += 1;
            cnts.append(cnt);



        res = 1;


        for cnt in cnts:
            res *= nCr(y + cnt - 1, cnt);
            res %= mod;


        res *= powers[y - 1]
        res %= mod;


        return res;


    print(solve())
