외로운 산

"이건 네 할아버지 스로르가 만든 거란다, 소린." 들뜬 목소리로 쏟아지는 드워프들의 질문에 그가 답했다. "산의 도면이지."

---

J. R. R. 톨킨, 호빗

외로운 산의 도면은 산을 서로 다른 두 투영면에 평행 투영한 그림 두 장이다. 두 투영면은 지면과 수직이고, 서로도 수직이다. 두 투영 모두 산 같은 모양이다.

빌보는 그 산을 본 적이 없어서 머릿속으로 그려 본다. 정말 산 하나가 외따로 서 있을까, 아니면 능선과 다른 산이 둘러싸고 있을까? 어느 쪽이든 드워프 왕국 전체를 품으려면 어마어마하게 클 것이다.

빌보는 간달프가 건넨 도면만 가지고 외로운 산과 그 주변 산이 차지할 수 있는 최대 부피를 가늠해 보기로 했다.

지면을 평면 $z = 0$에 두자. 첫 번째 투영은 $Oxz$ 평면에, 두 번째 투영은 $Oyz$ 평면에 그려져 있다. 점 $(x_1, z_1), \dots, (x_n, z_n)$으로 주어진 투영은, 이 점들을 순서대로 잇는 조각별 선형 함수 $f$에 대한 영역 $\{(x, z) : x_1 \le x \le x_n,\ 0 \le z \le f(x)\}$를 뜻한다.

$Oxz$ 평면으로의 평행 투영이 첫 번째 영역과 정확히 같고 $Oyz$ 평면으로의 평행 투영이 두 번째 영역과 정확히 같은 입체 가운데, 부피가 가장 큰 것의 부피를 구하자.

첫째 줄에 산을 $Oxz$ 평면에 평행 투영한 그림의 점 개수 $n_x$가 주어진다 ($2 \le n_x \le 100\,000$). 둘째 줄에 이 투영을 이루는 꺾은선의 좌표 $x_i, z_i$가 $n_x$쌍 주어진다 ($-10^9 \le x_1 < x_2 < \cdots < x_{n_x} \le 10^9$, $0 \le z_i \le 10^9$, $z_1 = z_{n_x} = 0$).

이어지는 두 줄에는 $Oyz$ 평면으로의 투영이 같은 형식으로 주어진다.

두 투영에 모두 맞는 입체가 없으면 Invalid plan을 출력한다.

그렇지 않으면 최대 부피는 유리수이다. 이 값을 기약분수 $p/q$로 쓰면, 위 제한에서 $q$는 결코 $1\,000\,000\,007$의 배수가 아니므로 $r \times q \equiv p \pmod{1\,000\,000\,007}$과 $0 \le r < 1\,000\,000\,007$을 만족하는 정수 $r$가 정확히 하나 있다. 그 $r$를 출력한다.