当前没有测试数据。

------------------------
I take this problem from my midterm exam today, because for me and some of my friends it's interesting, so I decided to translated this problem into English and upload this problem to SPOJ. See the original problem in Indonesian language here.
------------------------ 

Given N sectors where 1<N<10¹⁰⁰⁰, from a circle that sown in the picture below:

We will color each sector with K different colors, where 2<K<10¹⁰⁰⁰ such that each sector colored with one color and each adjacent sector must have different color. Your task is to count how many ways to color all that sectors.

Input

First line, there is a number T(0<T<1000) denoting number of test cases, then T lines follow.
each line containing two integers: N and K separated by a space.

Output

For each test case, output number of ways to color the circle, since the number can be too large, take modulo 10⁹+7.

Example

Input:
2
2 3
3 3
Output:
6
6

Explanation:

For the first case, we have two sectors and three colors, here is all possibilities:

For second test case, we have three sector and three colors, here is all possibilities:

Time limit set so that ~128 Bytes of python 3 code can get accepted, also my C top speed program AC in 0.12s
Have fun :) 

See also: Another problem added by Tjandra Satria Gunawan