נתון מערך $a$ המכיל $n$ מספרים שלמים. נוסף על כך, קיים מערך $b$ הריק בתחילה. חלק מהאיברים של $a$ יתווספו ל־$b$. כל איבר נוסף בהסתברות $P$, באופן בלתי תלוי באיברים האחרים. לאחר מכן מחשבים את ערכו של $s$:

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

כאשר $\oplus$ הוא XOR ברמת הסיביות (אם המערך $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