题目背景

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}$。

输出格式

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

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

524070430

55 96 4
396135414 150956526 115846323 684016411 478047433 741809293 841489850 30757425 354718 455244385 67265783 601148661 653297520 159551113 659259694 422602824 890944094 515558436 708977878 859628263 674258521 366153708 146971849 6161187 658301233 461136214 471709361 18786219 349277110 525215286 508995440 640141358 994347874 337617068 743448773 691546444 504640221 401810440 113565512 194628996 99765846 419008498 110931344 659189735 171012254 255189228 896007913 104632201 451664101 178069999 952991431 840513981 647057140 692809264 931718019 30010246 380306874 368517911 154597143 770763865 497641686 772741050 919136255 321190494 134863734 372165464 743950576 11194552 760810101 386902866 928594467 936096033 784108853 271133783 330481696 61402412 432546315 837809841 492881572 200968716 472860533 777800538 858285842 716767711 483244349 497540302 436003214 827152949 390815935 567741247 468900425 37709000 257282045 362991016 500424354 943931245 116395951

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$。