希望大家来帮帮忙
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.
