COCI '22 Contest 4 #3 Bojanje

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

Oliver is a rubber duck that not only finds bugs, but also likes to paint. His latest painting has $n$ ~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$ ~t~ iterations. In every iteration he will do the following steps:

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

Now, Oliver is afraid his painting will become monotonous or boring. He considers a painting good if there are at least $k$ ~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$ ~n~, $t$ ~t~, and $k$ ~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$ ~10^9 + 7~.

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

Constraints

Subtask	Points	Constraints
1	30	$k = n$ ~k = n~
2	40	$t \le 1\,000$ ~t \le 1\,000~
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}$ ~\frac{1}{2}~.

Sample Input 2

10 2 5

Sample Output 2

Explanation for Sample 2

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

Sample Input 3

3 141592653589793 2

Sample Output 3

468261332

Comments

There are no comments at the moment.