给定两个正整数 x 和 y。数组 F 称为 x 的 y 分解,当且仅当满足以下条件:
- F中有y个元素,且均为整数;
- $$\prod_{i=1}^{y} F_i = x$$。
您必须计算 x 的 y 分解的成对不同数组的数量。两个数组 A 和 B 被视为不同,当且仅当存在至少一个索引 i (1 ≤ i ≤ y) 使得 Ai ≠ Bi。由于答案可能非常大,因此将其打印为 109 + 7 模。
输入
第一行包含一个整数 q (1 ≤ q ≤ 105) — 要解决的测试用例的数量。
接下来是 q 行,每行包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ 106)。这些行中的每一行都代表一个测试用例。
输出
打印 q 个整数。第 i 个整数必须等于 xi 模 109 + 7 的 yi 分解次数。
示例
输入 #1
2 6 3 4 2
输出 #1
36 6
注意
在示例的第二个测试用例中,有六个 y 因子分解:
- { - 4, - 1};
- { - 2, - 2};
- { - 1, - 4};
- {1, 4};
- {2, 2};
- {4, 1}.