Description

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$.

Input Format

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 Format

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

8 8 3
3999 8477 9694 8454 3308 8961 3018 2255 4910

524070430

见 sample.zip/data2.in

见 sample.zip/data2.ans

Hint

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