On an infinitely large floor, you need to lay down an infinite number of tiles.

Each tile has a pattern of square cells of size $n \times n$. Each cell of the tile has an LED light strip fixed along its bottom and left borders, with different colors that create a colorful pattern.

The pattern on each tile is exactly the same. When laying the tiles, we will place an infinite number of tiles seamlessly next to each other, forming an infinitely large light strip pattern.

There are $k$ different colors available, and you need to choose corresponding colors for a total of $2n^2$ light strips on one tile, after which the other tiles will automatically replicate this coloring scheme. When laying the tiles, all tiles will be laid in the same direction, meaning they can be viewed as directly translating one tile and then stitching them together without rotation.

As you walk on the floor, you want to know how many essentially different schemes there are for coloring the tiles. Since the floor is infinite, and a person may face different directions (north, south, east, west) when observing the tiles, two schemes are defined as essentially the same if:

When observing the infinite floor plane created by the two schemes, if there exists a series of translations or rotations (excluding reflections) that can make the colors of the light strips at all positions on the floor completely identical, then these two schemes are considered essentially the same.

Input

There are multiple test cases in a single test file. The first line of the input contains a single integer $T$ ($1 \le T \le 10$), indicating the number of test cases.

For each test case:

• The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), representing the size of the pattern and the number of colors, respectively.

Output

For each test case, output a single line with a single integer, representing the number of essentially different schemes, modulo $10^9 + 7$.

Example

Sample Input 1

3
1 2
2 2
114514 5201314

Sample Output 1

3
31
377726028

Note

The following image shows 19 construction schemes for $n = k = 2$ (to better illustrate the tiling effect, each image shows 9 tiles arranged in a $3 \times 3$ pattern, with LEDs available in dark and light colors). By swapping the dark and light colors of the first 12 schemes, another 12 schemes can be obtained, resulting in a total of 31 schemes.