Consider a character set σ of size c. There are c^(2n) strings of length 2n, each of whose characters lies in σ. Let's call such a string perfect if the set of its indices {1, 2, .., 2n} can be partitioned into n pairs, such that:

• Each index is a part of exactly one pair
• For each pair (i, j), S[i] = S[j]
• No two pairs are entangled, that is, for any two pairs (i, j) and (k, l), i < k < j < l must NOT be true.

Given n and c, count the number of perfect strings of length 2n, modulo 10^9 + 7.

Input Format

• The first line contains T, the number of testcases. Then the testcases follow.
• Each testcase consists of two space separated integers, n and c.

Constraints

• 1 ≤ T ≤ 10^5
• 1 ≤ n, c ≤ 10^7
• The sum of n over all testcases doesn't exceed 10^7.

Sample 0

Input

2
3 1
2 2

Output

1
6

Explanation

• In the first testcase, there is only one string and it is clearly perfect
• In the second testcase, let the character set be {a, b}. The perfect strings are (along with a partition of their indices into pairs):
  • aaaa: {(1, 4), (2, 3)}
  • aabb: {(1, 2), (3, 4)}
  • abba: {(1, 4), (2, 3)}
  • baab: {(1, 4), (2, 3)}
  • bbaa: {(1, 2), (3, 4)}
  • bbbb: {(1, 2), (3, 4)}