← 返回题目列表

AtCoder · tenka1_2014_final_a

A. 花轮先生

中文机器翻译题面 查看原题

問題文

正整数 X 的 h 进数的表现满足以下条件时 X 就称为是塙先生。

  • 相同字符的出现次数为 n 次或以下。
  • w 位数。
  • 0 不以……开始。

塙先生的数量为 1000000007 (十进制)除的余数。


入力

输入将以以下形式从标准输入给出。

h n w
  • 三个整数 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, 1110 的 7 个满足条件。

1111 满足 1 是 4 出现回数,所以不是塙先生。


入力例2

10 3 18

出力例2

408595145