← 返回题目列表

Codeforces · 893/E

E. 计数数组

中文机器翻译题面 查看原题

给定两个正整数 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}.