Es gibt ein Array $a$ mit $n$ ganzen Zahlen. Außerdem gibt es ein anfangs leeres Array $b$. Einige Elemente von $a$ werden zu $b$ hinzugefügt. Jedes Element wird unabhängig von den anderen mit Wahrscheinlichkeit $P$ hinzugefügt. Anschließend wird der Wert $s$ berechnet:

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

Dabei bezeichnet $\oplus$ das bitweise exklusive Oder (wenn das Array $b$ leer ist, ist $s$ gleich null). Du sollst den Erwartungswert von $s^2$ berechnen.

Eingabe

Die erste Eingabezeile enthält drei ganze Zahlen $n$, $X$ und $Y$. Die Wahrscheinlichkeit $P$ ist gleich $\frac{X}{Y}$.

Die zweite Zeile enthält $n$ durch Leerzeichen getrennte ganze Zahlen $a_i$ — die Elemente des Arrays $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 $$

Ausgabe

Die Antwort lässt sich immer als Bruch $\frac{u}{v}$ darstellen, wobei $u$ und $v$ teilerfremd sind und $v \not\equiv 0 \pmod{10^9+7}$ gilt. Gib nur eine Zahl aus — $u \times v^{-1} \bmod (10^9+7)$.

Beispiele

Eingabe 1

3 1 2
2 8 10

Ausgabe 1

42