Source

This problem is adapted from Long Long OJ, and the copyright belongs to Codeforces.

Problem Source: https://codeforces.com/contest/893/problem/E

Problem Description

There are multiple test cases. For each test case, given $x$ and $y$, find the number of sequences of length $y$ whose product equals $x$.

Negative numbers are allowed in the sequence. Calculate the number of such sequences, modulo $10^9+7$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ ($1\le T\le 10^5$) — the number of test cases to solve.

The next $T$ lines each contain two integers $x_i$ and $y_i$ ($1\le x_i, y_i\le 10^6$). Each line represents a test case.

Output Format

Output $T$ integers. The $i$-th integer should be the number of sequences modulo $10^9+7$.

Samples

2
6 3
4 2

36
6

Sample Explanation

The possible sequences are as follows:

• $\{-4,-1\}$;
• $\{-2,-2\}$;
• $\{-1,-4\}$;
• $\{1,4\}$;
• $\{2,2\}$;
• $\{4,1\}$.