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⁹

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)