A string is called a "prime string" if it can't be written as concatenation of more than one same strings. For example, the following strings are not prime strings: AAA, ABABAB, CFGFGCFGFG, while CFGFGC, ABABA are prime strings.

Calculate the number of prime string of length N (1<=N<=1000000), and only contains first K (1<=K<=26) letters from English alphabet. Note that some of these K letters need not appear in that string.

Input

Multiple test cases. The number of them (about 10000) is given in the very first line.

Each test case contains one line with two integers - K and N, separated by a single space.

Output

For each test case, output the required number modulo 1000000007 in a single line.

Example

Input:
1
2 3

Output:
6

Explanation

The prime strings of length 3 which only contain character 'A' and 'B' are: AAB, ABA, ABB, BAA, BAB, BBA.

Constraints

1 <= N <= 1000000

1 <= K <= 26

Total number of test cases is around 10000.