Є масив $a$, що містить $n$ цілих чисел. Також є початково порожній масив $b$. Деякі елементи $a$ будуть додані до $b$. Кожен елемент додається з імовірністю $P$ незалежно від інших. Потім обчислюється значення $s$:

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

де $\oplus$ — побітове виключне АБО (якщо масив $b$ порожній, $s$ дорівнює нулю). Потрібно обчислити математичне сподівання $s^2$.

Вхідні дані

Перший рядок вхідних даних містить три цілі числа $n$, $X$ і $Y$. Імовірність $P$ дорівнює $\frac{X}{Y}$.

Другий рядок містить $n$ цілих чисел $a_i$, розділених пробілами, — елементи масиву $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 $$

Вихідні дані

Відповідь завжди можна подати як дріб $\frac{u}{v}$, де $u$ та $v$ взаємно прості і $v \not\equiv 0 \pmod{10^9+7}$. Потрібно вивести лише одне число — $u \times v^{-1} \bmod (10^9+7)$.

Приклади

Вхідні дані 1

3 1 2
2 8 10

Вихідні дані 1

42