Nam have an alphabet of size M (i.e alphabet consists of M different characters). He will construct all string of length N by using his alphabet. Hence, he have to construct M^N string in total. After construct all strings, Nam will categorize them into classes. Two strings must be in the same class if they are equivalent (see the definition below). But M^N is a large number, so he can't construct all strings in 1 or 2 days. So he need your help to calculate the number of classes.

In this problem, 2 strings of the same length A and B are consider equivalent if 2 following conditions are true for all 1 <= i, j <= length of strings:

1. (A_i != A_j) <=> (B_i != B_j)
2. (A_i = A_j) <=> (B_i = B_j)

where S_i denote the i-th (1 based-indexing) character of string S. It is easy to see that, if string A and B are equivalent, string B and C are equivalent, then string A and C are equivalent.

Input

The first line is T - the number of test cases. Then T test cases follow.

Each test is described in a single line contains 2 integers M and N.

Output

For each test cases, print the number of classes. Since this number can be large, you must print it modulo 10⁹ + 7.

Constraints

• 1 ≤ T ≤ 100000
• 1 ≤ M, N ≤ 2000