Problem Description
Declare:
k=∑mi=1φ(i∗n) mod 1000000007
n is a square-free number.
φ is the Euler's totient function.
find:
ans=kkkk...k mod p
There are infinite number of k
Input
Multiple test cases(test cases ≤100), one line per case.
Each line contains three integers, n,m and p.
1≤n,m,p≤107
Output
For each case, output a single line with one integer, ans.
Sample Input
1 2 6
1 100 9
Sample Output
4
7
http://blog.csdn.net/mengxiang000000/article/details/53574583