Migrated from Lutece 364 Easy Calculation

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

KO is a Taobao engineer at infrastructure team. He likes thinking, especially about math and algorithm problem. One day a math puzzle comes to his mind.

Let’s define an equation as follow:

$f_{1,j} = j, j \geq 1$ $f_{i,1} = 1, i \geq 1$ $f_{i,j} = f_{i,j-1}\times f_{i-1,j}, i > 1 \ and\ j > 1$

Given two integers $n$, $m$, how to calculate the value of $f_{n,m}$ mod $10^9$?

Input

The first line of the input is an integer $T$ ($T\leq 1000$), which stands for the number of test cases you need to solve.

Every test case are two integers $n$, $m$ ($1\leq n, m\leq 10^9$).

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and starts at $1$. Then the answer $f_{n,m}\rm\ mod\ 10^9$. See sample for more details.

Samples

4
1 2
2 2
2 3
3 3

Case #1: 2
Case #2: 2
Case #3: 6
Case #4: 12

Resources

The 9th UESTC Programming Contest Preliminary