eolymp
bolt
Try our new interface for solving problems
Problems

Double Necklace

Double Necklace

Time limit 3 seconds
Memory limit 64 MiB

Rabbit Stan again has forgotten about his wedding anniversary. How can he still congratulate Francine? Probably there is a chance to find that necklace which was lost long time ago. It was perfect ... shining, radiating happiness. It looked like a normal necklace with colored beads the same size. But THAT necklaces feature was that it consisted of two sets of beads instead of one. So we could represent beads in the necklace of length 5 like a sequence of numbers:

1 3 5 7 9

0 2 4 6 8

The adjacent beads in this necklace are: 0 and 1, 1 and 3, 2 and 4, 9 and 1 etc. Each particular bead has exactly three adjacent beads. Unfortunately, it’s not possible to find the original necklace, but you can try to produce the same as Francine had. Stan remembers only three facts: the length of the necklaces, the number of different colors that are used for making a necklace, and that no two adjacent beads were of the same color. Find the number of possible necklaces. Two necklaces are considered different if at least one position of beads vary in color. Numbering of beads is strict, since the beads 0 and 1 are always located near the hooks. Chances that Stan produces exactly THAT necklace are very low, because there are a lot of different necklaces. Therefore, the result can be easily output by module 10^9+7 (1000000007).

Input data

The first line contains a single number T (1T50000) – the number of tests. The following T lines contain two space separated integers each: n and c, where n (2n10^18) – the length of the necklace, and c (1c10^9) – the number of different possible colors.

Output data

Output one number in a separate line – the result for each particular test.

Examples

Input example #1
4
10 2
10 1
2 3
11 2
Output example #1
2
0
18
0
Source ACM-ICPC Ukraine 2012, 1st Stage Ukraine, April 21, 2012