P4491 [HAOI2018] Coloring

HAOI2018 Round 2 Problem 2.

To repay Xiao C for the apples, Xiao G plans to give art-loving Xiao C a canvas. This canvas can be abstracted as a sequence of length $N$, and each position can be painted with one of $M$ colors. However, Xiao C only cares about the number of colors that appear exactly $S$ times among the $N$ positions. If there are $K$ colors that appear exactly $S$ times, then Xiao C will gain happiness $W_k$. Xiao C wants to know, over all possible colorings, what the sum of the happiness he can obtain is, modulo $1004535809$.

Read from standard input. The first line contains three integers $N, M, S$. The next line contains $M + 1$ integers; the $i$-th number denotes $W_{i-1}$.

Output to standard output. Output a single integer representing the answer.

Special property: $\forall 1 \le i \le M, W_i = 0$. Constraints: For $100\%$ of the testdata, $1 \le N \le 10^7$, $1 \le M \le 10^5$, $1 \le S \le 150$, $0 \le W_i < 1004535809$.  Translated by ChatGPT 5