Solve the programming task below in a Python markdown code block.
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}.