Server Time: Sun Oct 22, 2017 6:33 am
Welcome ( logout
1419 - Necklace
  PDF (English) Statistics Forum
Time Limit: 4 second(s) Memory Limit: 32 MB

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 nth bead.

3)      The nth 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

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

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

Output

For each case, print the case number and the total number of possible necklaces modulo 1000000007.

Sample Input

Output for Sample Input

7

4 2

5 7

5 2

4 8

4 3

5 3

5 5

Case 1: 6

Case 2: 3367

Case 3: 8

Case 4: 1044

Case 5: 24

Case 6: 51

Case 7: 629

 


Problem Setter: Md. Mahbubul Hasan
Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan