問題文
正整数 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