Read problems statements in Mandarin Chinese and Russian.
Mike likes to invent new functions. The latest one he has invented is called SuperFunction. Let's consider how it can be calculated:

You are given two integers N and K. SuperFunction of N and K equals to the sum of K'th powers of the positive numbers, which are coprime with N and also not greater than N.

I.e. SuperFuntion of 6 and 3 equals to 1^{3} + 5^{3} = 126.

Mike knows how to calculate SuperFunction in case N and K are rather small integers. Now he wants you to write him a solution, which can calculate SuperFuntion for bigger constraints. As far as SuperFunction could be extremely huge, you are asked to do all the calculation under modulo M.

Help Mike!

------ Input ------

The first line contains three integers N, K and M.

------ Output ------

The first line of contains the only integer, denoting SuperFuntion of N and K under modulo M.

------ Example ------

Input:
5 2 100
Output:
30

------ Explanation ------

In the test case N equals to 5, K equals to 2, M equals to 100. The answer is (1^{2} + 2^{2} + 3^{2} + 4^{2}) mod 100 = 30.

------ Scoring ------

Subtask 1 (12 points): 1 ≤ N ≤ 100, 1 ≤ K ≤ 2, 1 ≤ M ≤ 40000;

Subtask 2 (28 points): 1 ≤ N ≤ 1 000 000, 1 ≤ K ≤ 2, 1 ≤ M ≤ 10^{9};

Subtask 3 (30 points): 1 ≤ N ≤ 1 000 000 000 000, 1 ≤ K ≤ 3, 1 ≤ M ≤ 10^{9};

Subtask 4 (30 points): 1 ≤ N ≤ 1 000 000 000 000, 1 ≤ K ≤ 10, 1 ≤ M ≤ 10^{18}.

见题面

见题面