bojanje — COCI CONTEST_#4
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 18
Algorithms: fast exponentiation, modular arithmetic, markov chain, combinatorics

# Croatian Open Competition in Informatics
# Round 4, February 11th 2023

# Task Bojanje
## 1 second / 512 MiB / 110 points

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 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 ≤ *i* ≤ *n*), and memorize the colour on the *i*-th part of the painting.
2. Again, Oliver will select uniformly at random an index *j* (1 ≤ *j* ≤ *n*). He will repaint the *j*-th part of the painting with the colour of the *i*-th part of the painting. If the *j*-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

The first line contains the numbers from the task statement *n*, *t* and *k* (2 ≤ *k* ≤ *n* ≤ 10, 1 ≤ *t* ≤ 10<sup>18</sup>).

### Output

In the first and only line output the answer modulo 10<sup>9</sup> + 7.

Formally, let *m* = 10<sup>9</sup> + 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$ (mod *m*). Output the integer equal to $p \cdot q^{-1}$ mod *m*. In other words, output such an integer *x* that 0 ≤ *x* < *m* and $x \cdot q \equiv p$ (mod *m*).

### Scoring

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

## Examples

| Input             | Input   | Input                  |
|-------------------|---------|------------------------|
| 2 1 2             | 10 2 5  | 3 141592653589793 2  |
| Output            | Output  | Output                 |
| 500000004         | 1       | 468261332              |

#### Clarification of the first example:

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

#### Clarification of the second example:

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.

Starter code: