Number of Factor Sequences

Problem Description

There are multiple test cases.

For each case you are given two numbers $X$ and $Y$. Count how many integer sequences of length $Y$ have product equal to $X$, i.e.

Note: two sequences are different if and only if they differ in at least one position with the same index. For example, $(1, 2)$ and $(2, 1)$ are considered different sequences.

The answer may be large, so output it modulo $10^9 + 7$.

For example: given $(X, Y) = (6, 2)$, the number $6$ can be written as $(\pm1, \pm6), (\pm2, \pm3), (\pm3, \pm2), (\pm6, \pm1)$ — eight length-$2$ sequences — so the answer is $8$.

Input Format

The first line contains an integer $T$, the number of test cases to follow.

Each test case contains two numbers $X$ and $Y$.

Output Format

For each test case, output one line: the answer.

Sample Input

4
6 2
6 3
6 4
1 4

Sample Output

8
36
128
8

Explanation: for test case 4, it is equivalent to assigning an even number of minus signs to $1$, so the answer is $\binom{4}{0} + \binom{4}{2} + \binom{4}{4} = 8$.

Constraints

• $1 \le T \le 10^5$
• $1 \le X, Y \le 10^6$