Submit | All submissions | Best solutions | Back to list |

## 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(10^{9}+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(10 ^{9}+7)**. But don’t modulo the final sum of divisor. See sample input and output for exact format.

### Example

Input:

3

2 5

14 1163 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 |