問題文

あなたはメイド喫茶「ぜろかん☀たいよー」で働くメイドです。 今日は常連のご主人様にタピオカミルクティーをお出しすることになりましたが、 その直前になって美味しくないタピオカを誤ってミルクティーに入れてしまったかもしれないことに気付きました。

タピオカは$N$粒あり，$1,2,\cdots ,N$の番号で区別されます。 タピオカ$i$の美味しさは正の整数$b_i$です。 今、タピオカ$1,2,\cdots ,M$がミルクティーの中に入っており、それ以外はキッチンにあります。 タピオカミルクティーの美味しさは、その中に入っているタピオカの美味しさの総和に等しいです。

あなたはちょうど$K$回だけ萌え萌えパワーを使ってタピオカを瞬間移動させることができます。 パワーを使う度に、粒ごと独立に$\frac{p}{q}$の確率で、ミルクティーの中のタピオカはキッチンに、 キッチンにあるタピオカはミルクティーの中に移動します。 ミルクティーの中とキッチンにあるそれぞれのタピオカの数は必ずしも保たれず、 瞬間移動が起こる確率は粒毎に独立で、パワーを使ったにもかかわらず$1$粒も移動しない場合があります。

ちょうど$K$回の萌え萌えパワーの行使ののち、 ご主人様にお出しするタピオカミルクティーの美味しさの期待値はいくらになるでしょうか？

期待値は有理数となり、 正整数$x$と${10}^9+7$の倍数でない正整数$y$で$\frac{x}{y}$と表せることが制約のもとで保証されます。 そして、$0\le R<{10}^9+7$かつ$x\equiv yRmod{10}^9+7$を満たす唯一の非負整数$R$を出力してください。

入力

$NMKpq$
$b_1$
$b_2$
$⋮$
$b_N$

ただし、与えられる入力は以下の制約に従います。 入力が多いので、Python等ではなくPyPy, C++等の高速な言語を用いることが推奨されます。

• $1\le N\le {10}^5$
• $0\le M\le N$
• $1\le K\le {10}^{12}$
• $1\le p<q\le {10}^9$
• $1\le b_i\le {10}^9$
• 入力はすべて整数

出力

問題文にある形式で期待値を出力し、 最後に改行してください。

サンプル

1 0 1 1 2
1

500000004

4 3 4 1 4
4
4
4
4

250000010

5 2 314159265358 1729 87539319
12345678
99999996
99999997
99999998
99999999

57524728