Server Time: Tue Aug 21, 2018 2:16 pm
 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.

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.

# 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