配点 : 400400

問題文

正の整数 A,B,CA, B, C が与えられます.Ax=By=zCAx = By = z^C が成立するような正の整数の組 (x,y,z)(x, y, z) は無数に考えられますが,このうち zz の最小値を求めてください.答えは非常に大きくなる可能性があるため 1000000007(=109+7)1000000007 \,(= 10^9 + 7) で割った余りで答えてください.

制約

  • 入力は全て整数
  • 1A,B10121 \leq A, B \leq 10^{12}
  • 1C31 \leq C \leq 3

入力

入力は以下の形式で標準入力から与えられます.

AA BB CC

出力

zz の最小値を 10000000071000000007 で割った余りを出力してください.

サンプル 1

入力
24 90 2
出力
60

サンプル 2

入力
24 90 3
出力
30

サンプル 3

入力
2147483647 1000000009 1
出力
294967266

10000000071000000007 で割った余りを求めることに注意してください.

提出


Go (1.21)