题目描述

金吒有 $n$ 颗灵珠，有红色和黄色两种，颜色分别是 $c_i$，红色灵珠的颜色为 $0$ ,黄色灵珠的颜色为 $1$。每颗红色灵珠有 $p$ 灵气，每颗黄色灵珠有 $q$ 灵气。现在金吒需要 $k$ 灵气，请问他有多少种灵珠使用方案。

答案可能很大，请对 $1e9+7$ 取模

输入格式

输入数据一共两行，第一行分别为 $n,p,q,k$

第二行一共 $n$ 个数，分别为 $c_i$

输出格式

输出数据只有一个整数，为金吒的灵珠使用方案

样例

4 1 1 2
0 1 1 1

11

提示

数据的规模与规定

对于 $100\%$ 的数据，保证 $1 \leq n,p.q,k \leq 20$, $1\leq c_i \leq 100$

出题人:Zzqyoung