AtCoder Regular Contest 050

C - LCM 111


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

数字の 1A 個並べてできる整数を x とします。また、数字の 1B 個並べてできる整数を y とします。xy の最小公倍数を M で割った余りを求めてください。

制約

  • 1≦A,B≦10^{18}
  • 2≦M≦10^9

入力

入力は以下の形式で標準入力から与えられる。

A B M

出力

xy の最小公倍数を M で割った余りを出力せよ。


入力例1

2 3 100

出力例1

21

11111 の最小公倍数は 1221 なので、それを 100 で割った余りは 21 となります。


入力例2

2 2 121

出力例2

11

入力例3

10000000000 1 10007

出力例3

825

入力値は 32 bit 整数型に収まらない場合があります。


Submit提出する