実行時間制限: 2 sec / メモリ制限: 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