题目描述
为了报答小 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)。