版权声明

本题版权归 Long Long OJ 所有。

题目描述

多组数据，对于每组数据，给出 $x$ 和 $y$，求一个长度为 $y$ 的序列，其乘积为 $x$。

序列中的数允许有负数，求这种序列的个数，对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行包含一个整数 $T$（$1\leq T\leq 10^{5}$）—— 需要解决的测试用例数量。

接下来有 $T$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$（$1\leq x_{i},y_{i}\leq 10^{6}$）。每一行代表一个测试用例。

输出格式

输出 $T$ 个整数。第 $i$ 个整数应等于序列的个数模 $10^{9}+7$。

样例

2
6 3
4 2

36
6

提示

样例 $1$ 解释：

可能的序列如下：

• $\{-4,-1\}$；
• $\{-2,-2\}$；
• $\{-1,-4\}$；
• $\{1,4\}$；
• $\{2,2\}$；
• $\{4,1\}$。