[HAOI2018] 染色

题目背景

HAOI2018 Round2 第二题

题目描述

为了报答小 C 的苹果,小 G 打算送给热爱美术的小 C 一块画布,这块画布可以抽象为一个长度为 $N$ 的序列,每个位置都可以被染成 $M$ 种颜色中的某一种。 然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数,如果恰好出现了 $S$ 次的颜色有 $K$ 种,则小 C 会产生 $W_k$ 的愉悦度。 小 C 希望知道对于所有可能的染色方案,他能获得的愉悦度的和对 $1004535809$ 取模的结果是多少。

输入输出格式

输入格式


从标准输入读入数据。第一行三个整数 $N, M, S$。 接下来一行 $M + 1$ 个整数,第 $i$ 个数表示 $W_{i-1}$。

输出格式


输出到标准输出中。输出一个整数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

524070430

输入样例 #2

见 https://www.luogu.org/paste/rxrv9utg

输出样例 #2

231524284

说明

特殊性质: $\forall 1 \le i \le m, W_i = 0$。 对于 $100\%$ 的数据,满足 $1 \le N \le 10 ^ 7$,$1 \le M \le 10 ^ 5$,$1 \le S \le 150$,$0 \le W_i < 1004535809$。 ![Data](https://cdn.luogu.com.cn/upload/pic/18057.png)