クソデカ Triangular Relationship

2 secs 1024 MB
magurofly

問題文


整数 が与えられます。 以下の正の整数を 個選び、そのうちどの つの数の和も の倍数であるようにするとき、このような選び方の通り数を で割ったあまりを出力してください。 なお、 のように同じ数を複数選ぶこともでき、また、 のように並び替えは別の選び方とみなします。

制約


  • 入力は全て整数である

入力


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

N M K

出力


答えを で割ったあまりを出力せよ。

入出力例1


入力1
3 3 2
出力1
9

が条件を満たします。

入出力例2


入力2
32861 1333 2916
出力3
882919901

で割ったあまりを出力してください。

Submit


Go (1.14)