Problem Background

HAOI2018 Round2 Question 2

Problem Description

To repay Xiao C's apple, Xiao G plans to gift a canvas to Xiao C, who loves art. This canvas can be abstracted as a sequence of length $N$, where each position can be dyed in one of $M$ colors.

However, Xiao C is only concerned with the number of colors that appear exactly $S$ times in the sequence of $N$ positions. If there are $K$ colors that appear exactly $S$ times, Xiao C will experience a happiness of $W_k$.

Xiao C wants to know the sum of happiness he can obtain for all possible dyeing schemes, modulo $1004535809$.

Input Format

Input is read from standard input. The first line contains three integers $N, M, S$.

The next line contains $M + 1$ integers, where the $i$-th number represents $W_{i-1}$.

Output Format

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

524070430

Sample Input #2

See sample.zip/data2.in

Sample Output #2

See sample.zip/data2.ans

Notes

Special Property: $\forall 1 \le i \le m, W_i = 0$.

For $100\%$ of the data, the conditions $1 \le N \le 10^7$, $1 \le M \le 10^5$, $1 \le S \le 150$, and $0 \le W_i < 1004535809$ are satisfied.

见题面 Input 部分

见题面 Output 部分