Problem Description

Oliver is a little yellow duck who not only can find bugs but also loves to paint. His latest painting consists of $n$ parts, each painted with a different color. After receiving many criticisms for his predictable artwork, he decided to modify his painting through $t$ iterations. In each iteration, he will perform the following operations:

• Oliver will uniformly randomly select an index $i\ (1\le i\le n)$, and remember the color of the $i$-th part of the painting.
• Oliver will then uniformly randomly select another index $j\ (1\le j\le n)$. He will paint the $j$-th part of the painting with the same color as the $i$-th part. If the $j$-th part already has the same color as the $i$-th part, no change will occur. Note that $i$ can be equal to $j$.

Now, Oliver is afraid that his painting might become too monotonous or boring. He believes a painting is good if it contains at least $k$ different colors. Please help him calculate the probability that the painting will be good after these modifications.

Input Format

The first line contains three integers $n, t, k\ (2\le k\le n\le 10, 1\le t\le 10^{18})$, as described in the problem statement.

Output Format

Output a single number, which is the answer modulo $10^9+7$.

Formally, let $m = 10^9+7$. It is known that the answer can be represented as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \pmod m$. Output $p \cdot q^{-1} \bmod m$. In other words, output the integer $x$ such that $0 \le x < m$ and $x \cdot q \equiv p \pmod m$.

Sample Input and Output

Sample Input #1

2 1 2

Sample Output #1

500000004

Sample Input #2

10 2 5

Sample Output #2

1

Sample Input #3

3 141592653589793 2

Sample Output #3

468261332

Notes/Hints

Sample 1 Explanation: The painting has two colors, so the probability that it remains the same after one iteration is $\frac{1}{2}$.

Sample 2 Explanation: After two iterations, the number of different colors cannot decrease from 10 to less than 5, so in any case, the painting will have at least 5 different colors.

见题面 Input 部分

见题面 Output 部分