Existe um vetor $a$ que contém $n$ inteiros. Existe também um vetor $b$ inicialmente vazio. Alguns elementos de $a$ serão adicionados a $b$. Cada elemento é adicionado com probabilidade $P$, independentemente dos outros. Em seguida, calcula-se o valor de $s$:

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

onde $\oplus$ é o OU exclusivo bit a bit (se o vetor $b$ estiver vazio, $s$ é igual a zero). Você deve calcular o valor esperado de $s^2$.

Entrada

A primeira linha da entrada contém três inteiros $n$, $X$ e $Y$. A probabilidade $P$ é igual a $\frac{X}{Y}$.

A segunda linha contém $n$ inteiros $a_i$ separados por espaços — os elementos do vetor $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 $$

Saída

A resposta sempre pode ser representada como uma fração $\frac{u}{v}$, em que $u$ e $v$ são primos entre si e $v \not\equiv 0 \pmod{10^9+7}$. Você deve imprimir apenas um número — $u \times v^{-1} \bmod (10^9+7)$.

Exemplos

Entrada 1

3 1 2
2 8 10

Saída 1

42