RHOOD - Robin Hood


I think all of you have seen the popular television series Robin Hood. You’ve heard about Robin Hood. He is a brave and kind-hearted man. He loves people very much. He wants to help the poor people. But he is working with Robin Hood team at this moment. So, he is too busy for shooting TV series. Although he’s a star and wants to help the poor, he is not rich as you think. Suddenly he took a decision about robbing a bank. He will rob the World Bank and distribute the money to poor countries. But the problem is how much money a country should be given. Some countries are developed, and some are developing. So, he sets a condition. Every country will be marked by a number (N) that represents countries’ ranks (if a rank is smaller that means those countries are developed or rich enough) and Robin Hood will take a number M randomly to calculate M^N. Since M^N can be much bigger, so calculate (M^N) modulo 1000000007(109+7). And finally he will calculate the sum of divisor of that number. Then he will give the money to that country.

Since Robin Hood is weak in programming. So, he asks for your help.

Input

The first line in the data set is an integer T (1 <= T <= 200) that represents the number of data collections that follow. Each data set contains two integers M, N (1 <= M, N <= 100)

Output

For each test case print the money that Robin Hood can give to the specific country. Since the power of M^N can be much bigger, (M^N) modulo 1000000007(109+7). But don’t modulo the final sum of divisor. See sample input and output for exact format.

Example

Input:
3
2 5
14 11
63 60

Output:
Case 1: 63
Case 2: 565976772
Case 3: 1174118400

hide comments
weathervane: 2017-01-20 15:16:59

"if a rank is smaller..." Smaller than what? "calculate the sum of divisor..." What divisor? Is each line a separate problem, or do they together make a single problem? The problem statement make NO SENSE at all.

Last edit: 2017-01-20 15:19:42
yashcoolhack: 2016-12-21 16:19:13

getting tle with python2.7 but ac with pypy

Francky: 2016-12-13 19:02:49

OK for language restrictions. But now you have to move your 'problems' to tutorial, aside the fact this one is a non-sense problem (just like adding an area with the age of the captain...), there are already tasks for modular exponentiation and sum of divisor, with much better constraints.
Those problems have to be moved soon to tutorial. Thanks for your comprehension.

Edit : Moved to tutorial by admins.

Edit 2 : Don't hide EB's comments too ; it's quite like deleting them !

Francky: 2016-12-13 10:53:51

OK for language restrictions. But now you have to move your 'problems' to tutorial, aside the fact this one is a non-sense problem (just like adding an area with the age of the captain...), there are already tasks for modular exponentiation and sum of divisor, with much better constraints.
Those problems have to be moved soon to tutorial. Thanks for your comprehension.

Edit : Moved to tutorial by admins.

Last edit: 2016-12-13 12:12:59
wisfaq: 2016-12-13 10:11:25

@asha, thanks for updating the language restrictions.
The rest of my comment still holds.

Last edit: 2016-12-13 10:11:48
ashacse42: 2016-12-13 03:44:48

Francky check the language restrictions. It's open for all.

Francky: 2016-12-12 23:33:41

+1
@psetter : hide this problem, move others to tutorial with all languages allowed (unless specific reasons explained ; it's spoj spirit). Please be more respectful with psolvers and EB. You should answer to comments and not delete them.

wisfaq: 2016-12-12 21:06:39

Please don't remove my comments,that's rather unpolite.
The problem IS nonsensical. Getting the divisors of (a^b mod 1000000007) doesn't have any meaning.

Moreover the problem has unnecessary language restrictions.
I first asked to move the problem to tutorial but now I think hiding it would be better,

Last edit: 2016-12-12 21:33:11

Added by:Asha
Date:2016-12-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:Problem Setter: Md. Ashraful Islam, Lecturer, Dept. of CSE, Varendra University