PowMod

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