## NAJDSCPC - Dr. Sheldon cooper and Pseudo code

You know Dr. Sheldon cooper!! He is brilliant physicists. He always try to invent new things and establish new theory. Today he has written a new pseudo code for his new theory.

Pseudo code:

{ take two integers x and n let ans := 1 for i = 1 to n: ans := ans * x let ans: = ans MODULO (10^{18}+7) }

But Dr. Sheldon cooper suddenly realized that, this is not optimized code. It takes too much time for providing correct answer. So he needs a better code for his work.

As a programmer you can help Dr. Sheldon cooper. You should write code that gives the correct answer in efficient time.

### Input

The first line of the input contains an integer T denoting the number of test cases. Each test case contain two space separated integer x and n. (0 ≤ x, n ≤ 10^18)

### Output

For each case, print the case number and the desired answer. And remember that answer should be modulo of (10^18+7).

### Sample

Input:3 2 3 5 3 10 5OutputCase 1: 8 Case 2: 125 Case 3: 100000

Authored By: Tanvir Hasan Anick

Added by: | Najmuzzaman |

Date: | 2014-10-25 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |