有一个包含 $n$ 个整数的数组 $a$。此外，还有一个初始为空的数组 $b$。数组 $a$ 中的某些元素将被添加到 $b$ 中。每个元素被添加的概率均为 $P$，且相互独立。随后计算 $s$ 的值：

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

其中 $\oplus$ 表示按位异或运算（若数组 $b$ 为空，则 $s$ 等于 0）。你需要计算 $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} \pmod{10^9 + 7}$。

样例

样例输入 1

3 1 2
2 8 10

样例输出 1

42