There is an array $a$ containing $n$ integers. Also, there is initially empty array $b$. Some elements of $a$ are going to be added to $b$. Each element is added with probability $P$ independently from others. Then the value of $s$ is to be computed:
$$ s = \bigoplus_{i=0}^{|b|} b_i $$
where $\oplus$ is bitwise exclusive OR (if the array $b$ is empty, $s$ equals to zero). You are required to compute the expected value of $s^2$.
Input
The first line of input contains three integers $n$, $X$ and $Y$. The probability $P$ is equal to $\frac{X}{Y}$.
The second line contains $n$ integers $a_i$ divided by spaces — elements of the array $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 $$
Output
The answer can be always represented as a fraction $\frac{u}{v}$ where $u$ and $v$ are co-prime numbers and $v \not\equiv 0 \pmod{10^9+7}$. You are required to output only one number — $u \times v^{-1} \bmod (10^9+7)$.
Examples
Input 1
3 1 2 2 8 10
Output 1
42