406564: GYM102441 F 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$$$.

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

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

3 1 2
2 8 10

42