問題文
整数 N,M,K が与えられます。
N 以下の正の整数を M 個選び、そのうちどの 2 つの数の和も K の倍数であるようにするとき、このような選び方の通り数を 109+7 で割ったあまりを出力してください。
なお、 (1,1,1) のように同じ数を複数選ぶこともでき、また、 (1,1,3) と (1,3,1) のように並び替えは別の選び方とみなします。
制約
- 1≤N,K≤109
- 3≤M≤109
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを 109+7 で割ったあまりを出力せよ。
入出力例1
(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
109+7 で割ったあまりを出力してください。