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 >= 1;


f[i][1] = 1, i >= 1;


f[i][j] = f[i][j-1] * f[i-1][j], i > 1 and j > 1;


Given two integers n, m, how to calculate the value of f[n][m] mod 109?
 

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

Every test case are two integers n, m (1 <= n, m <= 109).

 

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] mod 109. See sample for more details.
 

那个不是109，是1000000000，复制的时候错了。。

都没人来吗。。悲剧了。。

你这是C

可以用其他语言啊，只要能编出程序就好了。。呵呵