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$
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}$
For each case, output a single line with one integer, ans.