SuperFunction

All submissions for this problem are available.
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}.
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/SFUNC 
Tags  basicmaths, easymedium, exponentiation, inclusnexclusn, kostya_by, ltime07, subarr 
Date Added:  28112013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions