4529: 「HAOI2018」染色
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布,
这块画布可以抽象为一个长度为 $N$ 的序列, 每个位置都可以被染成 $M$ 种颜色中的某一种.
然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数,
如果恰好出现了 $S$ 次的颜色有 $K$ 种, 则小C会产生 $W_k$ 的愉悦度.
小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 $1004535809$ 取模的结果是多少.
输入
第一行三个整数 $N, M, S$.
接下来一行 $M + 1$ 个整数, 第 $i$ 个数表示 $W_{i-1}$.
输出
输出一行一个整数表示答案．
样例输入 复制
8 8 3
3999 8477 9694 8454 3308 8961 3018 2255 4910样例输出 复制
524070430提示
数据范围：对于 $10\%$ 的数据，$N \le 10, M \le 5$； 对于 $30\%$ 的数据，$N \le 100, M \le 100$； 对于另外 $10\%$ 的数据，$ M \le 1000$； 对于另外 $10\%$ 的数据，$ \forall 1 \le i \le M, W_i = 0$； 对于 $100\%$ 的数据，$N \le 10^7, M \le 10^5, S \le 150, 0 \le W_i < 1004535809$。