Good Array

tanvirtareq 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 nn and kk you have to tell the number of good arrays of length nn whose elements are between 11 and kk, inclusive.

Input

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

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

Output

For each test case output the answer modulo 109+710^9+7.

Sample

InputOutput
1
4 2
6

The following arrays are good for n=4n = 4 and k=2k = 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][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=4n = 4 and k=2k=2 are good.


Submit

Login to submit.

Statistics

64% Solution Ratio
AlfehsaniEarliest, 1M ago
nirjoy139Fastest, 0.0s
nh_nayeemLightest, 918 kB
beg123Shortest, 931B
Toph uses cookies. By continuing you agree to our Cookie Policy.