# Practice on Toph

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

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

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.

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.

For each query print the answer in a separate line.

Input | Output |
---|---|

6 2 11 6 4 3 7 1 100 11 21 30 5 | 2049 1394 2188 1 410854020 25170552 |

For Case 1: Note that all values are provided in modulo |

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.

Login to submit

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