题目描述

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

$$\sum_{S' \subseteq S \wedge |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 独家拥有在线测评使用权。