Source

This problem is moved from Long Long OJ (Copyright by Codeforces). All rights reserved.

Adapted from: 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 a positive integer $T\ (1\le T\le 10^5)$ representing the number of test cases to solve.

Each of the next $T$ lines contains two positive integers $x, y\ (1 \le x, y \le 10^6)$.

Output Format

For each test case, output a non-negative integer representing the answer.

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\}$.