#2527. 「HAOI2018」染色

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wearry

题目描述

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

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

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

输入格式

第一行三个整数N,M,SN, M, S.

接下来一行 M+1M + 1 个整数, 第 ii 个数表示 Wi1W_{i-1}.

输出格式

输出一行一个整数表示答案.

样例

样例输入

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

样例输出

524070430

数据范围与提示

对于 10%10\% 的数据,N10,M5N \le 10, M \le 5

对于 30%30\% 的数据,N100,M100N \le 100, M \le 100

对于另外 10%10\% 的数据,M1000M \le 1000

对于另外 10%10\% 的数据,1iM,Wi=0\forall 1 \le i \le M, W_i = 0

对于 100%100\% 的数据,N107,M105,SN,0Wi<1004535809N \le 10^7, M \le 10^5, S \le N, 0 \le W_i < 1004535809