Counting Arrays
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given two positive integer numbers x and y. An array F is called an y-factorization of x iff the following conditions are met:
- There are y elements in F, and all of them are integer numbers;
-
.
You have to count the number of pairwise distinct arrays that are y-factorizations of x. Two arrays A and B are considered different iff there exists at least one index i (1 ≤ i ≤ y) such that Ai ≠ Bi. Since the answer can be very large, print it modulo 109 + 7.
The first line contains one integer q (1 ≤ q ≤ 105) — the number of testcases to solve.
Then q lines follow, each containing two integers xi and yi (1 ≤ xi, yi ≤ 106). Each of these lines represents a testcase.
Print q integers. i-th integer has to be equal to the number of yi-factorizations of xi modulo 109 + 7.
Input
The first line contains one integer q (1 ≤ q ≤ 105) — the number of testcases to solve.
Then q lines follow, each containing two integers xi and yi (1 ≤ xi, yi ≤ 106). Each of these lines represents a testcase.
Output
Print q integers. i-th integer has to be equal to the number of yi-factorizations of xi modulo 109 + 7.
2
6 3
4 2
36
6
Note
In the second testcase of the example there are six y-factorizations:
- { - 4, - 1};
- { - 2, - 2};
- { - 1, - 4};
- {1, 4};
- {2, 2};
- {4, 1}.
20231121集训
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2023-11-21 19:00
- End at
- 2023-11-21 21:00
- Duration
- 2 hour(s)
- Host
-
SamuelXuch
- Partic.
- 15