33687번 - 로펭씰~~ 달링씰~~

문제

당신은 세계 최고의 포커 대회 World Of Legends - High-stakes Yearly All-in No-limit Gambling^WOLHYANG에서 우승을 차지했고, 이제 남은 일은 상금을 수령하는 것뿐이다! 하지만 세계 최고의 포커 대회답게 상금을 수령하는 과정조차 쉽지 않다. 상금은 다음과 같은 방식으로 결정된다.

• 책상 위에 $N$개의 카드가 일렬로 놓여 있다.
• $i$번째 카드의 앞면에는 1ドル,ドル 뒷면에는 $p^{A_i} \times q^{B_i}$가 적혀 있으며, 모든 카드는 처음에 앞면이 보이도록 놓여 있다.
• 사회자는 동전 던지기를 $N$번 진행한다.
  • $i$번째로 동전을 던졌을 때 뒷면이 나오면 사회자는 $i$번째 카드를 뒷면이 보이도록 뒤집는다.
  • 각 동전 던지기에서 앞면이 나올 확률과 뒷면이 나올 확률은 각각 $\frac{1}{2}$로 동일하다.
• $N$번의 동전 던지기가 모두 끝난 후, 보이는 면에 적힌 숫자들의 최소공배수만큼의 원화를 받을 수 있다.

똑똑한 당신은 문득 궁금해졌다. 당신이 받을 원화의 기댓값은 얼마일까?

입력

첫째 줄에 카드의 개수 $N$이 주어진다. $(1 \leq N \leq 200,000円)$

둘째 줄에 $p$와 $q$가 공백으로 구분되어 주어진다. $(2 \leq p,q \leq 100,000円;$ $p, q$는 서로소$)$

셋째 줄에 $A_1,\cdots, A_N$이 공백으로 구분되어 주어진다. $(0\leq A_i \leq 200,000円)$

넷째 줄에 $B_1,\cdots, B_N$이 공백으로 구분되어 주어진다. $(0\leq B_i \leq 200,000円)$

입력으로 주어지는 모든 수는 정수이다.

출력

당신이 받을 원화의 기댓값을 998ドル,244円,353円$으로 나눈 나머지를 출력하여라.

제한

노트

유리수를 기약분수로 나타냈을 때 $\frac{y}{x}$인 경우, 이 수를 소수인 $p$로 나눈 나머지는 $xz \equiv y \pmod{p}$을 만족하는 0ドル$ 이상 $p$ 미만의 정수 $z$이며, $x$가 $p$의 배수가 아닌 경우 이 값은 유일하다.

이 문제에서 당신이 받을 원화의 기댓값은 유리수이며, 분모가 998ドル,244円,353円$의 배수가 아님을 증명할 수 있다. 또한, 998ドル,244円,353円$은 소수이다.