当前没有测试数据。

题目描述

为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可以抽象为一个长度为 N 的序列, 每个位置都可以被染成 M 种颜色中的某一种.

然而小 C 只关心序列的 N 个位置中出现次数恰好为 S 的颜色种数, 如果恰好出现了 S 次的颜色有 K 种, 则小 C 会产生 Wk 的愉悦度.

小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 1004535809取模的结果是多少.

输入格式

从文件 color.in 中读入数据.第一行三个整数 N, M, S.

接下来一行 M + 1 个整数, 第 i 个数表示 Wi−1.

输出格式

输出到文件 color.out 中.输出一个整数表示答案．

样例输入 1

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

样例输出 1

524070430

样例输入输出 2

见选手目录下的 color/color2.in 与 color/color2.ans.

数据范围与约定

特殊性质: ∀1 ≤ i ≤ m, Wi = 0

对于 100% 的数据, 满足 0 ≤ Wi < 1004535809