A - 塙さん Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

正の整数 Xh 進数での表現が以下の条件を満たすとき X は塙さんであるという。

  • 同じ文字の出現回数は n 回以下である。
  • w 桁である。
  • 0 から始まらない。

塙さんの個数を 1000000007 (十進数) で割った余りを求めよ。


入力

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

h n w
  • 3つの整数 h,n,w がスペース区切りで 1 行に与えられる。
  • 2 \leq h \leq 64
  • 1 \leq n \leq 512
  • 2 \leq w \leq 2048

部分点

  • h \leq 36 かつ n \leq 4 かつ w \leq 4 のケースすべてに正解した場合、部分点として 10 点を与える。

出力

塙さんの個数を 1000000007 (十進数) で割った余りを十進数で標準出力に出力せよ。出力は 1 行とし、末尾には改行をいれること。


入力例1

2 3 4

出力例1

7

二進数表記で、 1000, 1001, 1010, 1011, 1100, 1101, 11107 つが条件を満たす。

111114 回出現するので塙さんではない。


入力例2

10 3 18

出力例2

408595145

Source Name

天下一プログラマーコンテスト2014 本戦