クソデカ Triangular Relationship

2 secs 1024 MB
magurofly's icon magurofly

問題文

整数 N,M,KN, M, K が与えられます。 NN 以下の正の整数を MM 個選び、そのうちどの 22 つの数の和も KK の倍数であるようにするとき、このような選び方の通り数を 109+710^9 + 7 で割ったあまりを出力してください。 なお、 (1,1,1)(1, 1, 1) のように同じ数を複数選ぶこともでき、また、 (1,1,3)(1, 1, 3)(1,3,1)(1, 3, 1) のように並び替えは別の選び方とみなします。

制約

  • 1N,K1091 \le N, K \le 10^9
  • 3M1093 \le M \le 10^9
  • 入力は全て整数である

入力

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

N M K

出力

答えを 109+710^9 + 7 で割ったあまりを出力せよ。

入出力例1

入力1
3 3 2
出力1
9

(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1),(3,3,3)(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1),(3,3,3) が条件を満たします。

入出力例2

入力2
32861 1333 2916
出力3
882919901

109+710^9+7 で割ったあまりを出力してください。

提出


Go (1.21)