Good Array

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

Input	Output
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.