配点 :

問題文


正の整数 が与えられます. が成立するような正の整数の組 は無数に考えられますが,このうち の最小値を求めてください.答えは非常に大きくなる可能性があるため で割った余りで答えてください.

制約


  • 入力は全て整数

入力


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

出力


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

サンプル 1


入力
24 90 2
出力
60

サンプル 2


入力
24 90 3
出力
30

サンプル 3


入力
2147483647 1000000009 1
出力
294967266

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

Submit


Go (1.14)