NAJDSCPC - Dr. Sheldon cooper and Pseudo code

no tags 

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 (1018+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 5

Output
Case 1: 8
Case 2: 125
Case 3: 100000

Authored By: Tanvir Hasan Anick


hide comments

Added by:Najmuzzaman
Date:2014-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64