$2^{(a^b)}$ を求めてください。ただし、答えは非常に大きくなることがあるので、素数 $k$ で割ったあまりを出力してください。

• $1 \leq a,b,k \leq 10^9+7$
• $a,b,k$ は全て整数である
• $k$ は素数である

入力は以下の形式で与えられます。

$a$ $b$ $k$

答えを一行に出力してください。