配点 : 400 点
問題文
正の整数 A,B,C が与えられます.Ax=By=zC が成立するような正の整数の組 (x,y,z) は無数に考えられますが,このうち z の最小値を求めてください.答えは非常に大きくなる可能性があるため 1000000007(=109+7) で割った余りで答えてください.
制約
- 入力は全て整数
- 1≤A,B≤1012
- 1≤C≤3
入力
入力は以下の形式で標準入力から与えられます.
出力
z の最小値を 1000000007 で割った余りを出力してください.
サンプル 1
サンプル 2
サンプル 3
入力
2147483647 1000000009 1
1000000007 で割った余りを求めることに注意してください.