Problem Description

Oliver is a little yellow duck who can not only find bugs but also likes painting. His latest painting has $n$ sections, and each section is painted with a different color. After that, he received a lot of criticism because his painting was too predictable. He decided to modify his painting for $t$ iterations. In each iteration, he will do the following:

1. Oliver uniformly randomly chooses an index $i\ (1\le i\le n)$, and then remembers the color of section $i$ in the painting.
2. Oliver uniformly randomly chooses an index $j\ (1\le j\le n)$. He repaints section $j$ to be the same color as section $i$. If section $j$ already has the same color as section $i$, then nothing changes. Note that $i$ may equal $j$.

Now, Oliver is afraid that his painting will become too plain or boring. He thinks a painting is good if it contains at least $k$ different colors. Please help him compute the probability that the final painting is good.

Input Format

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

Output Format

Output one number in a single line, representing the answer modulo $10^9+7$.

Formally, let $m=10^9+7$. It can be shown that the answer can be written 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$.

2 1 2

500000004

10 2 5

1

3 141592653589793 2

468261332

Hint

Explanation for Sample $1$: There are two colors in the painting, so after one iteration, the probability that the painting stays the same as before any operation is $\frac{1}{2}$.

Explanation for Sample $2$: After two iterations, it is impossible for the number of different colors to decrease from $10$ to less than $5$, so in all cases the painting will have at least $5$ different colors.

Translated by ChatGPT 5