PowMod

Problem Description

Declare: $k=\sum_{i=1}^{m} \varphi (i*n)\ mod\ 1000000007$ $n$ is a square-free number. $\varphi$ is the Euler's totient function . find: $ans=k^{k^{k^{k^{...^k}}}}\ mod \ p$ There are infinite number of $k$

Input

Multiple test cases(test cases $\leq 100$), one line per case. Each line contains three integers, $n, m$ and $p$. $1 \leq n, m, p \leq 10^{7}$

Output

For each case, output a single line with one integer, ans.

Sample Input

1 2 6
1 100 9

Sample Output

4
7

Author

HIT

Source

2016 Multi-University Training Contest 1