PowMod

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

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

Hint

wange2014

Source

2016 Multi-University Training Contest 1

提交代码