Дан массив $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