SP8428 BTCODE_J - Grid Tiling

Vikas is the chief interior designer incharge 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 atleast 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?

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'.

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.