# Good Array

SEC Inter University Juni...
Limits 1s, 512 MB

An integer array is a good array if we can make the whole array empty by applying the following operation an arbitrary number of times:

• in one operation, we can erase two adjacent elements from the array if those two elements are different.

For given $n$ and $k$ you have to tell the number of good arrays of length $n$ whose elements are between $1$ and $k$, inclusive.

## Input

First line contains one integer $t ( 1 \leq t \leq 20 )$— the number of test cases.

Each of the following $t$ lines contains two integers $n(1\le n \le 10^5)$ and $k(1\le k\le 10^5)$.

## Output

For each test case output the answer modulo $10^9+7$.

## Sample

InputOutput
1
4 2

6


The following arrays are good for $n = 4$ and $k = 2$: $[1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1]$.

No other arrays for $n = 4$ and $k=2$ are good.