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 KK. In response Karim would have to tell him the sum of all positive divisors of NN raised to the KKth power modulo (109+7)(10^9 + 7) i.e dNdKmod(109+7)\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 Q20Q \leq 20 , the number of queries Go will ask Karim.
The QQ lines contain two integers N1016N \leq 10^{16} and K1018K \leq 10^{18}.

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

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

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

1Q201\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: 111+211=20491^{11}+2^{11}=2049
For Case 2: 14+24+34+64=13941^{4}+2^{4}+3^{4}+6^{4}=1394
For Case 3: 17+37=21881^{7}+3^{7}=2188
For Case 4: 1100=11^{100}=1
For Case 5: 121+1121=4108540201^{21}+11^{21} = 410854020
For Case 6: 15+25+35+55+65+105+155+305=251705521^{5}+2^{5}+3^{5}+5^{5}+6^{5}+10^{5}+15^{5}+30^{5}=25170552\

Note that all values are provided in modulo (109+7)(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


45% Solution Ratio

ShafinEarliest, Jun '20

NOYON31Fastest, 0.0s

ShafinLightest, 131 kB

steinumShortest, 377B

Submit

Login to submit

Editorial

Solution 1: Sieve until ⌈MAXN⌉\lceil{\sqrt{\textit{MAXN}}}\rceil⌈MAXN​⌉ and save all the primes in ...

Toph uses cookies. By continuing you agree to our Cookie Policy.