After hearing about Bilbo's Ring that he found in the Misty Mountains, Karim the Hobbit decided to explore the mountains on his own in hopes of finding some treasures for himself. And there he encountered Gollum. Gollum, being hateful to Hobbits since Bilbo stole his precious and being a lover of puzzles challenged Karim to answer his queries (and the failure to do so will result in his death).

For each query he gave Karim two integers $N$ and $K$. In response Karim would have to tell him the sum of all positive divisors of $N$ raised to the $K$th power modulo $(10^9 + 7)$ i.e $\displaystyle \sum_{d|N} d^{K} \textbf{mod} (10^{9}+7)$.

Since Karim is a mere hobbit with no mathematical skills, he has asked you for help. Save Karim's life from the treacherous hands of the Gollum.

Input

The first line of the Input contains an integer $Q \leq 20$, the number of queries Go will ask Karim. The $Q$ lines contain two integers $N \leq 10^{16}$ and $K \leq 10^{18}$.

For Subtask 1: (5 points) $1 \leq N \leq 10^{8}$ and $0 \leq K \leq 25$

For Subtask 2: (10 points) $1 \leq N \leq 10^{8}$ and $0 \leq K \leq 10^{18}$

For Subtask 3: (85 points) $1\leq N \leq 10^{16}$ and $0 \leq K \leq 10^{18}$

$1\leq Q \leq 20$ for all three subtasks.

Output

For each query print the answer in a separate line.

Sample

Input

Output

6
2 11
6 4
3 7
1 100
11 21
30 5

2049
1394
2188
1
410854020
25170552

For Case 1: $1^{11}+2^{11}=2049$ For Case 2: $1^{4}+2^{4}+3^{4}+6^{4}=1394$ For Case 3: $1^{7}+3^{7}=2188$ For Case 4: $1^{100}=1$ For Case 5: $1^{21}+11^{21} = 410854020$ For Case 6: $1^{5}+2^{5}+3^{5}+5^{5}+6^{5}+10^{5}+15^{5}+30^{5}=25170552$\

Note that all values are provided in modulo $(10^9+7)$

Notes:

If you are going to use python, please select pypy as language. PyPy 7.1 (2.7) for Python 2.7 and PyPy 7.1 (3.6) for Python 3.