Background

The problem title is meant to lure you into clicking...

After the problem setter CYJian created too many “poison problems” and was D-ed to death, the OIers buried him under the 18th layer of hell...

Problem Description

It is known that there are $K$ guardians in hell. Each guardian has an ability value $a_i$. However, we do not know their exact ability values. We only know that the sum of their ability values is $N$. In hell, a guardian’s power is enhanced. Specifically, the power of each guardian is $a_i^M$.

Now given $N, M, K$, find the sum of the total power over all possible valid assignments.

Input Format

One line with three integers $N, K$ and $M$.

Output Format

One line with one integer, representing the sum of all possible power values that the guardians can produce, modulo $10 ^ 9+7$.

5 2 3

100

7 3 1

28

Hint

• Subtask 1 (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.

Please do not complain that the setter’s “poison problem” is designed to be tight on time limits. For each subtask, the time and memory limits are at least twice those of the official solution.

Since there is only one test case, it may be relatively weak, so the judging will use bundled tests every 5 points.

Translated by ChatGPT 5