$n$ 個の整数を含む配列 $a$ と、最初は空の配列 $b$ があります。$a$ のいくつかの要素を $b$ に追加します。各要素は、他の要素とは独立に確率 $P$ で追加されます。その後、$s$ の値を次のように計算します。

$$ s = \bigoplus_{i=0}^{|b|} b_i $$

ここで $\oplus$ はビット単位の排他的論理和です（配列 $b$ が空の場合、$s$ はゼロです）。$s^2$ の期待値を求めてください。

入力

入力の最初の行には、3 つの整数 $n$、$X$、$Y$ が含まれます。確率 $P$ は $\frac{X}{Y}$ です。

2 行目には、配列 $a$ の要素である $n$ 個の整数 $a_i$ が空白区切りで含まれます。

$$ 1 \le n \le 10^5 $$

$$ 0 \le X < 10^9 + 7 $$

$$ 0 < Y < 10^9 + 7 $$

$$ X \le Y $$

$$ 0 \le a_i < 10^9 + 7 $$

出力

答えは常に分数 $\frac{u}{v}$ として表せます。ここで $u$ と $v$ は互いに素で、$v \not\equiv 0 \pmod{10^9+7}$ です。$u \times v^{-1} \bmod (10^9+7)$ という 1 つの数だけを出力してください。

入出力例

入力 1

3 1 2
2 8 10

出力 1

42