Good Array

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:

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.