問題文


正整数 , , が与えられます。 ただし、 以上 未満かつ、 の約数です。

次のような条件を満たす、長さ の数列は何通りあるでしょう?

  • 数列の各要素は 以上 以下かつ、 でない整数である
  • 数列の要素の総和は の倍数である

答えを で割った余りを出力してください。

制約


  • 以上 未満の約数を つ以上持つ
  • の約数である
  • 入力はすべて整数である

入力


入力はすべて整数である。

出力


計算結果を一行に出力せよ。

サンプル


入力1
1 314 157
出力2
0

の場合は条件を満たす数列は存在しません。

入力2
2 200 100
出力2
198

かつ を満たす を使って と書くことができる数列だけが考えられます。

入力3
998244353998244353 9982 161
出力3
936931417

Submit


Go (1.14)