A Memory Of Summer

2 secs 1024 MB
sgsw

問題文


※( 追記)AC者数の観点から難易度を青から黄に格上げしました。

月の半ば、仲良しどうし、ふみかさんとありすさんは海辺にビーチバレーをしに来ていました。

人はビーチバレーをしている途中、海から長さの数列と自然数が流れ着いていることに気がつきました。

そこで、この数列と自然数を用いて夏の思い出づくりも兼ねて、ちょっとしたゲームを行うことにしました。

その内容は以下のようなものです。


◎ゲームは合計ターンにわたって行われるものとする。

各ターンでは人はビーチバレーでバトルをし、

▷ふみかさんが勝利した場合は、元の数列を数列に対して左から右向きへ累積和を取ったものに置き換える。その後、次のターンに移行する。

▷ありすさんが勝利した場合は、元の数列を数列に対して右から左向きへ累積和を取ったものに置き換える。その後、次のターンに移行する。

▷引き分けた場合は、何もせず次のターンに移行する。


なお、「ふみかさんが勝つ事象、ありすさんが勝つ事象、引き分ける事象」はそれぞれの比率で起こり、

各ゲームにおいてこれらの事象は互いに独立であるものとします。

ターン目終了後、最終的に得られる数列の総和の期待値を求めてください。

制約


・入力は全て整数値である

入力


入力は以下の形式で与えられます。

N K
A_1 A_2 ... A_N
P Q R

出力


この問題の制約下では、求めるべき期待値は以下のように一意に表せることが証明できます。

は素数で割り切れない

ここでは、を出力する代わりに、の範囲で一意に定まる、以上の自然数を出力してください。

最後に改行してください。

なお、などの低速な言語を用いる際は実行時間制限に間に合わない可能性がありますので、++等の高速な言語の使用を推奨します。

サンプル


入力1
4 1
1 2 3 4
50 50 0
出力1
25

題意より

確率で数列は

確率で数列は

となります。

この場合の最終的な数列の合計の期待値で与えられます。

入力2
4 2
1 2 3 4
50 50 0
出力2
499122239

題意より

確率で数列は

確率で数列は

確率で数列は

確率で数列は

となります。

この場合の最終的な数列の合計の期待値で与えられます。

入力3
4 1
1 2 3 4
25 25 50
出力3
499122194

題意より

確率で数列は

確率で数列は

確率で数列は

となります。

この場合の最終的な数列の合計の期待値で与えられます。

入力4
8 20210820
2 0 2 1 0 8 2 0
35 50 15
出力4
216450791

この場合、期待値はとても大きくなります。

入力5
10 1000000000
0 0 1 1 0 0 0 0 0 0
0 0 100
出力5
2

この場合、何回試合を繰り返したところでその全てが引き分けで終わるため、試合の回数いかんに関わらず試合終了後の数列の状態に変化はありません。

したがって、終了後の期待値です。

Submit


Go (1.14)