Cooking dishes

All submissions for this problem are available.
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 ≤ N1.
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.
Sample Input
3
2 2
2 3
1 3
Sample Output
2
18
6
Explanation
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. A_{0} can take three different values and for each value of A_{0}, B_{0} can take any of the other two values.
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
Author:  utkarsh_lath 
Tester:  
Editorial  http://discuss.codechef.com/problems/COOKFOOD 
Tags  ltime02, simplemath, utkarsh_lath 
Date Added:  12072013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 