Little T2 and Dead Cats

The planet earth has become peaceful again because all the cats are dead. An evil robot named Xorged wants to import some cats from planet GUNEA76/85 to make the earth sorrowful again. But here is our Hero, Little T2 who will save the world once again. She has to solve many puzzles to destroy Xorged. As, you are her sidekick, you have to help her with one puzzle that she has told you to solve.

You are given a KxN grid. You have two types of tiles. one is 1xK and another one is Kx1. You have infinite amount of them and they can not be rotated. You have to tell how many ways you can fill up the grid with these tiles. No two tiles can overlap with each other and every cell of the grid should be filled.

This number is very important because this is the decryption key of Xorged's secret files.

Input

Input starts with an integer, T, denoting the number of test cases. Each of the next T lines contains two integers K and N.

Constraints

Easy Sub-Task:
1 <= T <= 40
2 <= K <= 3
1 <= N <= 20

Medium Sub-Task:
1 <= T <= 10000
2 <= K <= 10
1 <= N <= 100000

Hard Sub-Task:
1 <= T <= 10000
2 <= K <= 10
1 <= N <= 1000000000

Output

For each test case print a line like this format Case X: Y. X denotes the case number and Y denotes the number of ways you can fill up the grid. This number can be huge so that you will print it modulo 1000000007 (1e9+7).

Sample

Input	Output
4 2 1 3 2 2 7 2 11	Case 1: 1 Case 2: 1 Case 3: 21 Case 4: 144