Senior Pan has two positive integers x and y, and she calls an array is a beautiful array if and only if it satisfies the following conditions:
The elements in the array are integers.
The length of the array is exactly y.
The product of each element is exactly x.
Senior Pan wants you to help her calculate the number of beautiful arrays for different x and y.Two arrays A and B are considered different if there exists a position i that A_i ≠ B_i .
The answer can be very large, so you can just tell her the number mod 10⁹+7.
For example, if x is 2 and y is 2, there are four beautiful arrays: [1, 2], [2, 1] ,[−1, −2], [−2, −1].

The first line is an integer T, denoting the number of test cases.
For the following T lines, each line contains two positive integers x and y.
1 ≤ T ≤ 10⁵,  x, y ≤ 2 ∗ 10⁶

Output T lines, each line contains an integer, representing the number of beautiful array mod 10⁹+7.