Hay un arreglo $a$ que contiene $n$ enteros. También hay un arreglo $b$ inicialmente vacío. Se añadirán algunos elementos de $a$ a $b$. Cada elemento se añade con probabilidad $P$, de forma independiente de los demás. A continuación, se calcula el valor de $s$:

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

donde $\oplus$ es la disyunción exclusiva bit a bit (si el arreglo $b$ está vacío, $s$ es igual a cero). Debes calcular el valor esperado de $s^2$.

Entrada

La primera línea de la entrada contiene tres enteros $n$, $X$ e $Y$. La probabilidad $P$ es igual a $\frac{X}{Y}$.

La segunda línea contiene $n$ enteros $a_i$ separados por espacios: los elementos del arreglo $a$.

$$ 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 $$

Salida

La respuesta siempre se puede representar como una fracción $\frac{u}{v}$, donde $u$ y $v$ son coprimos y $v \not\equiv 0 \pmod{10^9+7}$. Debes imprimir un único número: $u \times v^{-1} \bmod (10^9+7)$.

Ejemplos

Entrada 1

3 1 2
2 8 10

Salida 1

42