問題文

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

制約

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

入力例1

2 3 100

出力例1

21

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

入力例2

2 2 121

出力例2

11

入力例3

10000000000 1 10007

出力例3

825

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