#6183. 看无可看

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

题目描述

最后的一刻我看到了......
一片昏暗?
我记起来了,
我看到,那里有一个集合 S ,集合 S 中有 n 个正整数 a[i] \ (1 \leq i \leq n)
我看到,打破昏暗的密码:

\sum_{S' \subseteq S\ 且\ \ |S'|=k}f\left(\sum_{x \in S'}x\right)

记忆中的 f 是一个数列,对于 i \gt 1 它满足 f(i) = 2 \times f(i-1) + 3 \times f(i-2)
给出 n,k,f(0),f(1) a[i] ,求上述式子的值,由于答案很大,输出答案对 99991 取模的结果即可。

输入格式

第一行两个正整数 n k
第二行 n 个正整数 a[i] 1 \leq a[i] \leq10^9
第三行两个正整数 f(0) f(1) 1 \leq f(0),f(1) \lt 99991

输出格式

一行一个数表示式子的值对 99991 取模的结果,详情见题目描述。

样例

样例输入 1

4 2
1 2 1 3
1 1

样例输出 1

234

样例解释 1

f=\{1,1,5,13,41,121,365,1093,3281,9841...\}
a[1] a[2] ,则 f(a[1]+a[2])=13
a[1] a[3] ,则 f(a[1]+a[3])=5
a[1] a[4] ,则 f(a[1]+a[4])=41
a[2] a[3] ,则 f(a[2]+a[3])=13
a[2] a[4] ,则 f(a[2]+a[4])=121
a[3] a[4] ,则 f(a[3]+a[4])=41
\mathrm{ans}=13+5+41+13+121+41=234

样例输入 2

20 10
125 3162 3261 152 376 238 462 4382 376 4972 16 1872 463 9878 688 308 125 236 3526 543
1223 3412

样例输出 2

32071

样例输入 3, 4

见附加文件

样例输出 3, 4

见附加文件

数据范围与提示

对于 20\% 的数据, 1 \leq n \leq 20
对于另外 10\% 的数据,满足 f(0)=f(1)=1
对于另外 20\% 的数据,满足 1 \leq n \leq 5000
对于另外 20\% 的数据,满足所有 a[i] 的和 \leq 10000 1 \leq n \leq 100
对于 100\% 的数据, 1 \leq n \leq 100000,1 \leq a[i] \leq 10^9,1 \leq f(0), f(1) \lt 99991

鸣谢纪中红太阳 Samjia2000 授权本 OJ 独家拥有在线测评使用权。