You are a necklace maker. You like this task because it's challenging, fascinating and of course makes a lot of money. Now, you want to make a necklace consisting of n beads. The beads are connected in the following fashion:

1. Bead i (1 < i < n) is connected with bead i - 1 and bead i + 1.
2. The first bead is connected with the second bead and the n^th bead.
3. The n^th bead is connected with the first bead and the (n-1)^th bead.

Now you have K colors and each bead can be colored using one of the K colors. You have to find the number of possible necklaces you can make using these colors. Two necklaces will be considered same if one can be rotated to another.

For example, say there are 4 beads in the necklace and you have two colors yellow and green, then there are 6 possible necklaces. They are:

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing two integers: n and K (1 ≤ n ≤ 1000, 1 ≤ K ≤ 10⁹).

For each case, print the case number and the total number of possible necklaces modulo 1000000007 (10⁹ + 7).