PowMod
TimeLimit:1500MS MemoryLimit:262144KB
64-bit integer IO format:%I64d
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.