PowMod

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.

1 2 6
1 100 9

4
7

HIT

2016 Multi-University Training Contest 1