Taco Sequences

You are given two integers, n and k. Consider sequences that follow a special rule: when k = 1, there is exactly one valid sequence; when k > 1 and even, the number of valid sequences is \( (n-1)^{\frac{k}{2}} \) modulo \(10^9+7\); and when k is odd (with k > 1), there is no valid sequence (i.e. the answer is 0).

Your task is to compute the number of unique sequences for given values of n and k using these rules.

Note: All answers should be given modulo \(10^9+7\).

inputFormat

The first line of the input contains an integer T denoting the number of test cases. Each of the following T lines contains two space-separated integers n and k.

outputFormat

For each test case, output a single line containing the number of unique sequences modulo \(10^9+7\>.

## sample

3
3 2
4 3
2 5

2
0
0

</p>