P9174 [COCI 2022/2023 #4] Bojanje

Oliver is a little yellow duck who can not only find bugs but also likes painting. His latest painting has $n$ sections, and each section is painted with a different color. After that, he received a lot of criticism because his painting was too predictable. He decided to modify his painting for $t$ iterations. In each iteration, he will do the following: 1. Oliver uniformly randomly chooses an index $i\ (1\le i\le n)$, and then remembers the color of section $i$ in the painting. 2. Oliver uniformly randomly chooses an index $j\ (1\le j\le n)$. He repaints section $j$ to be the same color as section $i$. If section $j$ already has the same color as section $i$, then nothing changes. Note that $i$ may equal $j$. Now, Oliver is afraid that his painting will become too plain or boring. He thinks a painting is good if it contains at least $k$ different colors. Please help him compute the probability that the final painting is good.

The first line contains three integers $n,t,k\ (2\le k\le n\le 10,1\le t\le 10^{18})$, with meanings as described in the statement.

Output one number in a single line, representing the answer modulo $10^9+7$. Formally, let $m=10^9+7$. It can be shown that the answer can be written as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q\not\equiv 0 \pmod m$. Output $p\cdot q^{-1}\bmod m$. In other words, output the integer $x$ such that $0\le x

Explanation for Sample $1$: There are two colors in the painting, so after one iteration, the probability that the painting stays the same as before any operation is $\frac{1}{2}$. Explanation for Sample $2$: After two iterations, it is impossible for the number of different colors to decrease from $10$ to less than $5$, so in all cases the painting will have at least $5$ different colors. | Subtask ID | Additional Constraints | Score | |:-:|:-:|:-:| | $0$ | Sample | $0$ | | $1$ | $k=n$ | $28$ | | $2$ | $t\le 1000$ | $36$ | | $3$ | No additional constraints | $36$ | Translated by ChatGPT 5