Senior Pan has two positive integers xand 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 xand y.Two arrays Aand Bare considered different if there exists a position ithat A _i ≠ B _i.
The answer can be very large, so you can just tell her the number mod 10 ⁹ +7.
For example, if xis 2and yis 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 Tlines, each line contains two positive integers xand y.
1 ≤ T ≤ 10 ⁵, x, y ≤ 2 ∗ 10 ⁶

OutputTlines, each line contains an integer, representing the number of beautiful array mod10⁹+7.