版权声明

本题搬运自 Long Long OJ，版权归 Codeforces 所有。

题目来源：https://codeforces.com/contest/893/problem/E

题目描述

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

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

输入格式

本题有多组数据。

第一行一个正整数 $T\ (1 \le T \le 10^5)$ 表示数据组数。

对于每组数据，输入一行两个正整数 $x, y\ (1 \le x, y \le 10^6)$。

输出格式

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

样例

2
6 3
4 2

36
6

样例解释

可能的序列如下：

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