多组数据。

每组给定两个数 $X, Y$，问有多少个长度为 $Y$ 的整数序列之乘积为 $X$，即

$$\prod_{i = 1}^Y f_i = X$$

注意：两序列不同，当且仅当至少有一个下标相同的位置不同。如 $(1, 2), (2, 1)$ 被视作不同的序列。

答案可能很大，将其模以 $10^9 + 7$ 输出。

例如：给定 $(X, Y) = (6, 2)$。可以将 $6$ 分成 $(\pm1, \pm6), (\pm2, \pm3), (\pm3, \pm2), (\pm6, \pm1)$ 八种长度为 $2$ 的序列，因此答案是 $8$。

输入格式

第一行一个整数 $T$，表示接下来有 $T$ 组数据。

每组数据包含两个数字 $X, Y$。

输出格式

对于每组数据，输出一行，表示答案。

样例输入

4
6 2
6 3
6 4
1 4

样例输出

8
36
128
8

解释：对于数据四，相当于将偶数个负号分配给 $1$，因此答案为 $\displaystyle\binom{4}{0} + \displaystyle\binom{4}{2} + \displaystyle\binom{4}{4} = 8$

数据规模

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