Problem Background

The title of the problem is designed to attract your attention...

Our problem setter, CYJian, has been struck dead for setting too many toxic problems. OIers have buried him beneath the eighteenth layer of hell...

Problem Description

It is known that there are \( K \) guardians in hell, each with a power value \( a_i \). However, we do not know their exact power values, only that the sum of their power values is \( N \). In hell, the power of the guardians is enhanced, specifically, each guardian's power becomes \( a_i^M \).

Given \( N \), \( M \), and \( K \), you are asked to find the sum of the possible power values of all guardians.

Input Format

A single line containing three integers \( N \), \( K \), and \( M \).

Output Format

A single integer representing the sum of the possible power values of all guardians modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

5 2 3

Sample Output #1

100

Sample Input #2

7 3 1

Sample Output #2

28

Notes/Hints

Subtask1 (20 pts):

\( 1 \leq N, M \leq 10 \)

\( 1 \leq K \leq N \)

Subtask 2 (40 pts):

\( 1 \leq N, M \leq 4096 \)

\( 1 \leq K \leq N \)

Subtask 3 (40 pts):

\( 1 \leq N, M \leq 10000 \)

\( 1 \leq K \leq N \)

All \( a_i \) must be positive integers.

Do not complain about the problem setter's toxic time constraints; each subtask's time and space limits are at least twice those of the standard solution.

Since there is only one set of data, it may be relatively weak, so testing is done in bundles of 5 points each.

见题面 Input 部分

见题面 Output 部分