Double Necklace#3207
Stan the rabbit has once again forgotten about his wedding anniversary. How can he congratulate Francine? Perhaps there is still a chance to find that necklace which was lost a long time ago. It was beautiful, shining, radiating happiness. It looked like a normal necklace made of beads of the same size but of different colors. However, the unique feature of THAT necklace was that it consisted of two rows of beads instead of one. For clarity, we can number the beads in a necklace of length as follows:
1 3 5 7 9
0 2 4 6 8
In this necklace, the adjacent beads are: 0 and 1, 1 and 3, 2 and 4, 9 and 1, and so on. Each bead has exactly three adjacent beads. Unfortunately, it is no longer possible to find the original necklace, but Stan can try to make one just like Francine had. Stan remembers only three things: the length of the necklace, the number of different colors used to make the 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 bead differs in color at some position). The numbering of the beads is fixed, since beads 0 and 1 are always located near the clasp. The chances that Stan makes exactly THAT necklace are very low, as there are many different possibilities. Therefore, output the result modulo 10^9+7 ().
The first line contains a single integer (1 \leq T \leq 50000) — the number of tests. Then follow lines, each containing two space-separated integers: and , where (2 \leq n \leq 10^{18}) is the length of the necklace, and (1 \leq c \leq 10^9) is the number of different colors available at the factory.
For each test, output a single number on a separate line — the answer to the problem.
Example 1