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)


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

hide comments
2022-12-07 06:37:47 Ishan
is less than 5 states possible ?

==(Francky)==> No, 5 is the limit.

Last edit: 2023-03-19 22:09:09
2017-02-10 13:59:15 Francky
Now it is Python doable.
2013-03-18 13:22:54 Aditya Muraletharan
I'm getting a TLE with eight states :(
--ans(francky)--> It's not a secret anymore that you can find some relations in your 8 states, so you'll can have lower order : 6 or 5 will be enough. After that, it is only code opti. Good luck.

Reply: Thank you. Managed to reduce it to six states:) Coming up with the initial states is a great exercise!

Last edit: 2013-03-19 08:13:34
2012-12-30 06:31:09 (Tjandra Satria Gunawan)(曾毅昆)
Thanks Francky, I'll try your suggestion :-)
2012-12-29 18:26:37 Francky
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...
--
To speak more about this problem : for me the fun was mostly to find with pencil & paper the formula of order 6.

Last edit: 2012-12-29 18:29:07
2012-12-29 07:56:53 (Tjandra Satria Gunawan)(曾毅昆)
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
I wonder how can Francky solve this problem in 0.03s... Or, maybe my formula is too complex (3KB code,150 lines)..
2012-12-28 20:16:55 (Tjandra Satria Gunawan)(曾毅昆)
FINALLY AFTER 10 HOURS WORKING ON BRUTEFORCE PROGRAM, FORMULA ORDER 5 FOUND! I'll solve this problem soon! ;-)
2012-07-12 09:25:50 Francky
Order is 5, not less.
It can be found with four "easy" states of order two, so we have order 8, but it can be further reduced to 5 by analysis, and not more.
Really fun problem.
2012-05-27 19:16:04 :D
Great problem. It's seems pretty standard, but coming up with proper formulas is really challenging and fun!

Small hint: number of "states" can be reduced to 6, maybe less.

Last edit: 2012-05-27 19:26:11
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.