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 \le i \le n\)), and memorize
the colour on the \(i-th\) part od the painting.
2. Again, Oliver will select uniformly at random an index \(j\) (\(1 \le j \le n\)). He
will repaint the \(j-th\) part of the painting with the colour of the \(i-th\) part od 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\) differents colours on it. Help him calculate the probability that his painting will be
good at the end.

Subtask 1 (30 points): \(k = n\)

Subtask 2 (40 points): \(t \le 1\,000\)

Subtask 3 (40 points): No additional constraints.

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}\)).

In 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 ^{p}
\(q\) ^{,}
where \(p\) and \(q\) are integers and \(q\)̸ ≡0
(mod \(m\)). Output the integer equal to \(p \cdot q\)^{−} mod \(m\). In other
words, output such an integer \(x\) that \(0 \le x < m\) and \(x \cdot q\) ≡\(p\)
(mod \(m\)).

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 4