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 he got a lot of critiques that his painting is too predictable, he decided to modify his painting in $t$ iterations. In every iteration he will do the following steps:

1. Oliver will select uniformly at random an index $i$ $(1\le i\le n)$, and memorize the colour on the $i^{\text{th}}$ part of the painting.
2. Again, Oliver will select uniformly at random an index $j$ $(1\le j\le n)$. He will repaint the $j^{\text{th}}$ part of the painting with the colour of the $i^{\text{th}}$ part of the painting. If the $j^{\text{th}}$ part is already painted in that colour, there is no change. Note that $i$ can be equal to $j$.

Now, Oliver is afraid his painting will become monotonous or boring. He considers a painting good if there are at least $k$ different colours on it. Help him calculate the probability that his painting will be good at the end.

Input Specification

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

Output Specification

On the first and only line, output 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(\mathrm{mod}m)$. Output the integer equal to $p\cdot q^{-1}modm$. In other words, output an integer $x$ such that $0\le x<m$ and $x\cdot q\equiv p(\mathrm{mod}m)$.

Constraints

Subtask	Points	Constraints
1	30	$k=n$
2	40	$t\le 1000$
3	40	No additional constraints.

Sample Input 1

2 1 2

Sample Output 1

500000004

Explanation for Sample 1

There are two colours on the painting, so the probability that it remains the same after one iteration is $\frac{1}{2}$.

Sample Input 2

10 2 5

Sample Output 2

1

Explanation for Sample 2

After two iterations, the number of different colours can't go from $10$ to less than $5$, so in every case the painting will have at least $5$ different colours.

Sample Input 3

3 141592653589793 2

Sample Output 3

468261332