Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Karim Meets Gollum

By hsiam261 · Limits 3s, 512 MB

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

InputOutput
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.

Discussion

Statistics


41% Solution Ratio

ShafinEarliest, 1M ago

NOYON31Fastest, 0.0s

ShafinLightest, 131 kB

Sobi777Shortest, 1058B

Submit

Login to submit

Editorial

Solution 1: 1. Sieve until $\lceil{\sqrt{\textit{MAXN}}}\rceil$ and save all the primes in a list wh...