Problem Description

A positive integer $ X $ is called Hanako-san if its representation in base $ h $ satisfies the following conditions:

• The same digit appears at most $ n $ times.
• It has exactly $ w $ digits.
• It does not start with a $ 0 $.

Find the number of Hanako-san numbers modulo $ 1000000007 $ (decimal).

Input Format

The input is given from the standard input in the following format:

$ h $ $ n $ $ w $

• Three integers $ h $, $ n $, and $ w $ are given in one line separated by spaces.
• $2 \leq h \leq 64$
• $1 \leq n \leq 512$
• $2 \leq w \leq 2048$

Output Format

Output the number of Hanako-san numbers modulo $ 1000000007 $ (decimal) to the standard output. The output should be a single line, and a newline should be included at the end.

Sample Input and Output

Sample Input #1

2 3 4

Sample Output #1

7

Sample Input #2

10 3 18

Sample Output #2

408595145

Notes/Hints

Partial Points

• If all cases where $h \leq 36$, $n \leq 4$, and $w \leq 4$ are correctly solved, $ 10 $ points will be awarded as partial credit.

Sample Explanation 1

In binary notation, $ 1000, 1001, 1010, 1011, 1100, 1101, 1110 $ are the $ 7 $ numbers that satisfy the conditions. $ 1111 $ is not a Hanako-san because the digit $ 1 $ appears $ 4 $ times.

见题面 Input 部分

见题面 Output 部分