题目描述

若若的听歌口味很杂，所以若若通常采用随机播放的方式。

具体来说，若若的歌单中有 $n$ 首歌。由于若若对每首歌的喜爱程度不同，所以每首歌都有一个权值，第 $i$ 首歌的权值为 $p_i$。

当若若打开随机播放的模式后，播放器首先会随机选出一首歌，第 $i$ 首歌被选中的概率为 $\frac{p_i}{\sum p}$。

由于若若不想将一首歌连续听多遍，所以从第二首歌开始，每首歌都一定与前一首歌不同（但可能和更早播放的歌曲重复），即第 $i$ 首歌被选中的概率是：

$$\begin{cases} \frac{p_i}{(\sum p) - p_{last}}, & i \neq last \\ 0. & i = last \end{cases}$$

$last$ 为前一首被选出歌曲的编号。

现在若若想知道：当播放了 $m$ 首歌后，第 $t$ 首歌恰好被选中 $k$ 次的概率。

输入格式

第一行四个非负整数，$n$ ($2 \leq n \leq 10$)，$m$ ($1 \leq m \leq 8,000$)，$t$ ($1 \leq t \leq n$)，$k$ ($0 \leq k \leq \lceil \frac{m}{2} \rceil$)，用一个空格隔开，分别表示若若的歌单中有 $n$ 首歌曲，询问播放了 $m$ 首歌后，第 $t$ 首歌被选中 $k$ 次的概率。

第二行有 $n$ 个正整数，用一个空格隔开，第 $i$ 个数 $p_i$ ($1 \leq p_i \leq 10^6$) 表示第 $i$ 首歌的权值。

输出格式

设答案为 $\frac{x}{y}$，请输出一个非负整数 $z$ ($0 \leq z < 10^9 + 7$) 满足 $x \equiv y \cdot z \pmod {10^9+7}$。

可以证明这样的非负整数 $z$ 是唯一的。

样例

样例输入

2 3 1 2
2 1

样例输出

666666672