Painting

Oliver is a rubber duck that not only finds bugs but also likes to paint. His latest painting has $n$ parts, each coloured with a unique colour. After receiving many critiques that his painting is too predictable, he decided to modify it in $t$ iterations. In every iteration he does the following steps:

1. Oliver selects an index $i$ ($1 \le i \le n$) uniformly at random and memorizes the colour of the $i$-th part.
2. Oliver then selects an index $j$ ($1 \le j \le n$) uniformly at random and repaints the $j$-th part with the colour of the $i$-th part. If the $j$-th part already has that colour, nothing changes. Note that $i$ can be equal to $j$.

Oliver is afraid his painting will become monotonous or boring. He considers a painting good if it has at least $k$ different colours. Calculate the probability that his painting is good at the end.

The first line contains the numbers from the task statement $n$, $t$ and $k$ ($2 \le k \le n \le 10$, $1 \le t \le 10^{18}$).

Print the answer modulo $10^9 + 7$.

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

Clarification of the first example: The painting has two colours, so the probability that it stays the same after one iteration is $\frac{1}{2}$.

Clarification of the second example: After two iterations, the number of different colours cannot drop from 10 to less than 5, so in every case the painting has at least 5 different colours.