COCI '22 Contest 4 #3 Bojanje

View as PDF

Submit solution

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 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 \pmod{m}. Output the integer equal to p \cdot q^{-1} \bmod m. In other words, output an integer x such that 0 \le x < m and x \cdot q \equiv p \pmod{m}.


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

Sample Input 1

2 1 2

Sample Output 1


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


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



There are no comments at the moment.