On dispose d’un tableau $a$ contenant $n$ entiers. Il existe aussi un tableau $b$ initialement vide. Certains éléments de $a$ seront ajoutés à $b$. Chaque élément est ajouté avec une probabilité $P$, indépendamment des autres. On calcule ensuite la valeur de $s$ :

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

où $\oplus$ désigne le OU exclusif bit à bit (si le tableau $b$ est vide, $s$ vaut zéro). Vous devez calculer l’espérance de $s^2$.

Entrée

La première ligne de l’entrée contient trois entiers $n$, $X$ et $Y$. La probabilité $P$ est égale à $\frac{X}{Y}$.

La deuxième ligne contient $n$ entiers $a_i$ séparés par des espaces : les éléments du tableau $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 $$

Sortie

La réponse peut toujours s’écrire sous la forme d’une fraction $\frac{u}{v}$, où $u$ et $v$ sont premiers entre eux et $v \not\equiv 0 \pmod{10^9+7}$. Vous devez afficher un seul nombre : $u \times v^{-1} \bmod (10^9+7)$.

Exemples

Entrée 1

3 1 2
2 8 10

Sortie 1

42