/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
MMNMMさんはplatypusくんとニム屋の屋台でニムで遊ぶことにしました．
ニムとは，複数の石の山を使って遊ぶゲームで，プレイヤーは先手と後手に分かれます．
プレイヤーは自分の手番に次のことをすることができます．
- 石の山から一つの山を選び，その山にある石のいくつかを取り去る．
石がなくなり，石を取ることができなくなったプレイヤーが負けです．
platypusくんは十分頭がいいので常に最良の手を打ちます．
しかし，MMNMMさんはうっかり者なので確率 1 - p/q で最良の手を打ち，確率 p/q で最悪の手を打ちます．(どちらになるかは毎手番ごとに独立に判定されます)
2人はこの事実を知っています．
ここで，最良の手とは自分の打てる手のうち，それを打ったときに勝つ確率が最大となるものであり，最悪の手とはそれを打った時に勝つ確率が最小となるものです．
MMNMMさんは先手です．
MMNMMさんがplatypusくんに勝てる確率を既約分数 P/Q で表します．
このとき， 0 以上 10^9+7 未満の整数 M であって MQ と P をそれぞれ 10^9 + 7 で割ったあまりが等しいようなもの (つまり，p = 10^9 + 7 での Q の \mathbb{Z}/p\mathbb{Z} における逆元 Q^{-1} に対する PQ^{-1}) がただ1つ存在します．
M を求めてください．
制約
すべてのテストケースは以下の制約を満たします．
- 1 \leq N \leq 10^5
- 1 \leq a_i \leq 10^{12}
- 0 \leq p \leq q \leq 10^9
- 1 \leq q
- p と q は互いに素である
入力
入力は以下の形式で標準入力から与えられる．
N p q a_1 a_2 ... a_N
- 1行目には，整数 N ， p ， q がこの順に空白を区切りとして書かれている．これは，ニム山が N 個あり，MMNMMさんが最悪の手を p/q の確率で打つことを表している．
- 2行目には，整数 a_i (1 \leq i \leq N) がこの順に空白を区切りとして書かれている．これは， i 番目のニム山にははじめ a_i 個の石があることを表している．
出力
標準出力に，MMNMMさんがplatypusくんに勝てる確率を P/Q としたときの，\mathbb{Z}/p\mathbb{Z} における P \times Q^{-1} を1行に出力しなさい．
入力例 1
1 1 2 3
出力例 1
500000004
一回目でMMNMMさんがすべての石をとれなければ負けるので，MMNMMさんが勝つ確率は 1/2 です．
1 と 2 \times 500000004 を 10^9+7 で割ったあまりは等しいので，500000004を出力してください．
入力例 2
3 1 2 1 1 1
出力例 2
1
入力例 3
4 1 10 3 2 5 4
出力例 3
0
入力例 4
10 1 100 3 14 15 9 2 6 5 35 8 9
出力例 4
135181044