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 & 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 John Snow 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


Added by:Asha
Date:2016-12-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:MAWK BC C C++ 4.3.2 CPP14 COFFEE DART FORTH JAVA KTLN OCT PROLOG R RACKET SQLITE SWIFT UNLAMBDA
Resource:Problem Setter: Md. Ashraful Islam, Lecturer, Dept. of CSE, Varendra University

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.