KPOWERSUM - Kth Power Summation


Leeana Learned Few New Things Few Days Ago , Like:

1)      Find The Summation Of Divisors.

2)      Modular Arithmetic

So Now Her Uncle Gave Her A Task.

Task Is: You Will Be Given A Number(N) And Another Number(K). Now You Have To Find  Kth Power Summation Of Divisors Of N.

Summation Of All Divisors Of N Will Be Huge,  So You Have To Print The Summation Module (M=1000000007).

Like: Divisors Of 6 is: ( 1 2 3 6 ) And K = 2.
so, summation is: 1^K+2^K+3^K+6^K = 1^2 + 2^2 + 3^2 + 6^2= 1+4+9+36 = 50%1000000007=50

Leeana Thinks That You Are A Great Programmer, So She Needs Your Help. Can You Help Her??? :D :D :D 

Input

Input Starts With An Integer T (≤ 500), Denoting The Number Of Test Cases. Each Case Contains An Integer N (1 ≤ N ≤ 1015) And An Integer K (1 ≤ K ≤ 105) Denoting The Power Of Divisors.

Output

For Each Test Cases, Print The Case Number And The Kth Power Summation  Of Divisors Of N Module 1000000007. After Each Case Print A New Line. See Sample Input And Output For Better Explanation. Cool

Example

Input:
4
6 2
6 1
6 4
6 3
Output:
Case 1: 50
Case 2: 12
Case 3: 1394
Case 4: 252

#Extra_Challenge: N<=10^18, T<=1000 TL: 1s Tongue out


hide comments
shubham_001: 2018-09-06 20:02:08

Giving TLE , can you tell expected time complexity?

bdezso: 2018-09-06 07:48:08

Could you check my last submission? :/ TLE with formula.

>>Reply<<: it's seems like correct.but did you checked highest prime number or highest input??

(bdezso reply): Yes i checked :/ I wrote a test method as you can see, program was executed under ~7s... :/ i dont know whats the problem with my code.

Last edit: 2018-09-06 21:55:27
[Lakshman]: 2018-09-05 11:28:26

Not sure why I am getting wrong answer now. @RaYHan may I have a test case where my new code is failing.

Reply: i don't understand what you said ("my I have a test case where my new code is failing."). some users already got Accepted.

==Lakshman==> It was some typo. Yes, I saw some user got AC.
>>Rayhan<< : why you print extra newline after each test case??

Last edit: 2018-09-05 22:21:14
Kata: 2018-09-05 10:54:51

Did you fixed the test cases for judge, not just the sample? I do not think my code was wrong.
Edit: nvm, I misread the limits.
Reply: :)

Last edit: 2018-09-05 14:48:13
chhavi96: 2018-09-03 17:06:59

time limit is very strict....
i have tried to optimise everything but still TLE..

Reply: yes, it is. because you have to optimize/generate new formula. if time limit is not strict than you can submit a normal solution & get AC. so this(every) problem made for learn something new.

Last edit: 2018-09-03 18:28:05
rayhan50001: 2018-09-03 16:00:59

oh sorry. thank you. :(

bdezso: 2018-09-03 15:23:01

yes, test cases are wrong.

Reply: i think it's correct.
Reply2: Yes, now correct :)
(Rayhan) Reply: :)

Last edit: 2018-09-05 14:22:26
[Lakshman]: 2018-09-03 11:04:03

Are you sure test cases are correct?. In sample test cases T should be 4, not 2.

Reply: your output are different after each compilation.
check your code for highest input.

Last edit: 2018-09-03 16:13:07

Added by:RaYHan
Date:2018-09-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem