BTCODE_J  Grid Tiling
Vikas is the chief interior designer in charge of the Taj Palace, Mumbai. He wants to make an impressive and colourful pattern in the courtyard. Importing exotic tiles has become very difficult after the Mumbai terror attacks, and therefore Vikas has only 4 kinds of tiles to choose from:
A B C D == == == == XX X X X XX X XX
Any rotation of above tiles is also permitted.
Each tile is available in 'k' different colors, and there's an infinite supply of all tiles. The courtyard has dimensions 2 * 'n'. Vikas wants to tile the courtyard in such a way that no two adjacent tiles have the same color. Two tiles are considered adjacent if they share a common side. Two tilings are considered different if:
1) The arrangement of tiles is different.
2) There is at least 1 position (1*1 square) which has different colors in the two arrangements.
Can you help Vikas find the number of different ways in which he can tile the courtyard, subject to the above conditions?
Input
The first line of input contains a single integer 't', denoting the number of test cases.
Each of the next 't' lines contains 2 space separated integers 'n' and 'k'.
Output
For each test case output one integer, denoting the number of different ways in which the courtyard can be tiled.
Two tiles are considered adjacent if they share an edge. Two tiles which just share a common point are not considered adjacent.
Since the answers can be large, print all the quantities modulo 1000000007.
Constraints:
t <= 1000
1 <= n <= 10^9
1 <= k <= 1000
Example
Input: 2 1 1 1 2 Output: 1 4
Explanation:
Test case 1: There is only 1 way to tile the courtyard, by using a 2*1 tile.
Test case 2: Let '1' and '2' be the available colors. The grid can be tiled in 4 ways  1) place one 2*1 tile of color '1', 2) place one 2*1 tile of color '2', 3) Place two 1*1 tiles (color '1' above and color '2' below), 4) Place two 1*1 tiles (color '2' above and color '1' below)
hide comments
Ishan:
20221207 06:37:47
is less than 5 states possible ?


Francky:
20170210 13:59:15
Now it is Python doable. 

Aditya Muraletharan:
20130318 13:22:54
I'm getting a TLE with eight states :(


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121230 06:31:09
Thanks Francky, I'll try your suggestion :) 

Francky:
20121229 18:26:37
I didn't use my fastest code for this one (only the order 5 formula and a "little special trick", with full magic options, I think 0.00s is possible), I recommend for those (like tjandra) who want to try ultra speed methods, to challenge my SPP chrono (or SEQ in python) ; they are very good problems on that kind, my code for them are highly optimized, it's the key for many other problems. As always for those problems, I recommend to do them in Python (when possible), I use very classic I/O methods. There's still FLIB that I can't do in Python, but I have to try some new ideas, I'm not so far I think...


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121229 07:56:53
Finally solved! 0.11s in C with fast I/O and without precomputation. This is the hardest recurrence problem that I have solved on SPOJ! 10 Hours to find out the formula (trial and error with my slow BruteForce program), and 9 Hours to implement It (because so many bug on the formula) :O


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121228 20:16:55
FINALLY AFTER 10 HOURS WORKING ON BRUTEFORCE PROGRAM, FORMULA ORDER 5 FOUND! I'll solve this problem soon! ;) 

Francky:
20120712 09:25:50
Order is 5, not less.


:D:
20120527 19:16:04
Great problem. It's seems pretty standard, but coming up with proper formulas is really challenging and fun!

Added by:  suhash 
Date:  20110226 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode 2011, NIT Trichy, India 