No.995 タピオカオイシクナーレ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 128 MB / 通常問題
タグ : / 解いたユーザー数 123
作問者 : ganmodokixganmodokix / テスター : monkukui2monkukui2
17 ProblemId : 3171 / 出題時の順位表
問題文最終更新日: 2020-02-21 23:00:49

問題文

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

タピオカは$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 \lt 10^9+7$かつ$x \equiv yR \bmod{10^9+7}$を満たす唯一の非負整数$R$を出力してください。

入力

$N\ M\ K\ p\ q$
$b_1$
$b_2$
$\vdots$
$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 \lt q \le 10^9$
  • $1\le b_i \le 10^9$
  • 入力はすべて整数

出力

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

サンプル

サンプル1
入力
1 0 1 1 2
1
出力
500000004

入れ忘れたタピオカが$1$回のパワーの行使で瞬間移動する確率は$\frac{1}{2}$です。

サンプル2
入力
4 3 4 1 4
4
4
4
4
出力
250000010

求める期待値は$\frac{33}{4}$なので、$33\equiv 4R\bmod{10^9+7}$を満たす$0$以上$10^9+7$未満の唯一の整数$R=250000010$を出力します。

サンプル3
入力
5 2 314159265358 1729 87539319
12345678
99999996
99999997
99999998
99999999
出力
57524728

オーバーフローに注意してください。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。