As you might know, cooking is the process of taking a food item and subjecting it to various processes(like heating, roasting, baking etc).
A food item gets prepared after it has been subjected to exactly N processes.
The order in which the processes are applied matters(heating and then baking is different from baking and then heating). Also, the same processes cannot be aplied twice in succession. For example, heating → baking → heating is allowed, but heating → heating → baking is not allowed because 'heating' comes twice in succession.

Any given sequence A_{1}, A_{2}, A_{3}, ... A_{N} of N processes can be used to cook a food item if and only if A_{i} ≠ A_{i+1} for all 1 ≤ i ≤ N-1.

The chefs kitchen has got K equipments for K different processes.

Chef has to cook two dishes in parallel.
This means that if the first dish is prepared by applying processes A_{1}, A_{2}, A_{3}, ... A_{N} in this order, and the second dish made by processes B_{1}, B_{2}, B_{3}, ... B_{N}, then A_{i} ≠ B_{i} for any 1 ≤ i ≤ N, because otherwise chef would need two equipments for the process A_{i}.

Needless to say, 1 ≤ A_{i}, B_{i} ≤ K, no two consecutive elements of A are same, and no two consecutive elements of B are same.

Given N, K your task is to find the number of ways in which in which he can prepare the two dishes. Since the number of ways can be very huge,  you have to report it modulo 1000000007.

------  Input Description ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case is described by line containing two space separated integers, N and K as per the problem description.

------  Output Description  ------ 

For each Test case, output a separate line containing the answer modulo 1000000007.

------ Constraints ------ 

$T ≤ 100 $
$1 ≤ N, K ≤ 10^{9}$

Subtask 1 (30 points):  
N, K ≤ 5

------ Subtask 2 (20 points): ------ 

N, K ≤ 10000

the answer(without taking modulo 1000000007) will be at most 10^{4}.

Subtask 3 (25 points):  
N, K ≤ 10000

Subtask 4 (25 points):  
No special constraints

----- Sample Input 1 ------ 
3
2 2
2 3
1 3
----- Sample Output 1 ------ 
2
18
6
----- explanation 1 ------ 
For first test case, there are two ways: 
a) A = {1, 2} and B = {2, 1} and b) A = {2, 1} and B = {1,2}.

For third test case, A and B are of length 1. A0 can take three different values and for each value of A0, B0 can take any of the other two values.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions:
from sys import stdin
MOD = 1000000007
for trial in range(int(stdin.readline())):
	(N, K) = map(int, stdin.readline().split())
	Kmod = K % MOD
	K1mod = (K - 1) % MOD
	K2mod = (K - 2) % MOD
	if K == 1:
		print(0)
	elif K == 2:
		print(2)
	else:
		inner = (Kmod * K1mod * K1mod % MOD + Kmod * K1mod * K2mod * K2mod % MOD) % MOD
		if N == 1:
			print(K * (K - 1) % MOD)
		elif N == 2:
			print(inner)
		else:
			print(inner * pow(K ** 2 - 3 * K + 3, N - 2, MOD) % MOD)