23528번 - Random XOR 다국어

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 = \oplus_{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}$.

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$.

The answer can be always represented as a fraction $\frac{u}{v}$ where $u$ and $v$ are co-prime numbers and $v \neq 0 \mod (10^9+7)$ You are required to output only one number --- $u \times v^{-1} \mod (10^9+7)$

• $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$