Problem I

Counting Necklaces

A necklace is consisted of N identical beads and your job is to color the beads. Note that, in necklace the beads are arranged circularly, that is – first bead is adjacent to second bead, second bead is adjacent to third one, …, last one is adjacent to first one. Each bead should be colored with exactly one color and you have K different types of colors available. Now a coloring of the necklace is considered beautiful if for any three adjacent beads all of them have different colors.

Given three integers N, K and M: find how many different beautiful colorings are possible for an N-bead necklace where you have K different types of colors available. Output the result modulo M (%M). Two ways of coloring are considered different if it is not possible to have same color sequence of beads by rotation. For example, when N = 4, K = 4, "1234", "2341","3412" and "4123" are all same.

Input

First line of the input contains an integer T (T <= 100) which is the number of test cases. Each of the following T lines contain three integers N (3 <= N <= 10⁸), K (1 <= K <= 10⁸) and M (2 <= M <= 10⁸).

Output

For each test case, output the case number, followed by the number of beautiful colorings modulo M (%M).

Sample Input	Output for Sample Input
3 4 4 10000000 3 3 1000007 8 10 100000	Case 1: 6 Case 2: 2 Case 3: 99160

For the first case, the different ways are: "1234", "1324", "1423", "1243", "1342", "1432".

For the second case, the different ways are: "213" and "123".

Problemsetter: Tasnim Imran Sunny

Special Thanks: Tanaeem M Moosa, Md. Mahbubul Hasan