30706번 - KCPC 개최하기

문제

KCPC는 고려대학교의 ALPS, AlKor, MatKor 세 동아리가 연합하여 개최한다.

고려대학교는 이차원 평면으로 나타낼 수 있다. 이 평면 위의 격자점에 여러 건물이 있으며, 각 건물은 ALPS, AlKor, MatKor 중 한 동아리가 관리한다. 각 건물에는 서로 다른 모양의 도장이 있다.

KCPC를 개최하기 위해서는 서류에 ALPS, AlKor, MatKor의 순서대로 도장을 받아야 한다. 따라서 MatKor 회장인 동우는 ALPS, AlKor, MatKor 순서대로 각각이 관리하는 건물 중 하나씩을 고른다. 고른 세 건물을 각각 $A,ドル $B,ドル $C$라 하면, 동우는 건물 $C$에서 출발하여 $A,ドル $B$를 거쳐 다시 $C$로 돌아오며 도장을 받아 서류를 완성한다.

동우는 서류를 완성하는 과정에서 에너지를 소모하게 되는데, 에너지 소모량은 다음과 같이 계산한다:

기본적으로 두 건물 사이의 거리의 제곱의 합, 즉, $\overline{AB}^2+\overline{BC}^2+\overline{CA}^2$ 만큼의 에너지를 소모한다.

그리고 동우는 왼쪽 다리가 길기 때문에 시계방향으로 회전하는 것이 편하다. 이에 따라 에너지를 덜 소모하거나 더 소모하는데, 세 건물의 위치가 $S_{\triangle ABC}$의 넓이를 가진 삼각형을 이룬다고 할 때, $A,ドル $B,ドル $C$가 순서대로 시계방향을 이룬다면 2ドルS_{\triangle ABC}$만큼의 에너지를 덜 소모하며, 반시계방향을 이룬다면 2ドルS_{\triangle ABC}$만큼의 에너지를 더 소모한다. 세 점이 한 직선 위에 있다면 덜 소모하거나 더 소모하는 에너지는 없다.

동우는 세 건물을 선택할 수 있는 모든 경우마다 서류를 완성하고자 한다. 건물들의 위치가 주어졌을 때, 동우가 건물을 선택할 수 있는 모든 경우에 대해 서류를 완성하기 위해 필요한 동우가 소모하는 총 에너지를 구하여라. 총 에너지는 각각의 서류를 완성하기 위해 필요한 에너지 값의 합이다. 정답이 매우 클 수 있으므로 10ドル^9+7$로 나눈 나머지를 출력하자.

입력

첫 번째 줄에 ALPS, AlKor, MatKor의 순서대로 각 동아리가 관리하는 건물의 개수 $N,M,K(1\le N,M,K\le 500,000円)$이 주어진다.

다음 줄부터 $N$줄에 걸쳐 ALPS가 관리하는 건물의 좌표 ${x_a}_i,{y_a}_i$가 주어진다.

다음 줄부터 $M$줄에 걸쳐 AlKor가 관리하는 건물의 좌표 ${x_b}_i,{y_b}_i$가 주어진다.

다음 줄부터 $K$줄에 걸쳐 MatKor가 관리하는 건물의 좌표 ${x_c}_i,{y_c}_i$가 주어진다.

모든 좌표의 절댓값은 10ドル^9$ 이하의 정수이며, 위치가 같은 두 건물이 존재하지 않는다.

입력되는 데이터의 양이 많음에 유의하자.

출력

첫 줄에 동우가 건물을 선택할 수 있는 모든 경우에 대해 서류를 완성할 때 필요한 총 에너지를 10ドル^9+7$로 나눈 나머지를 출력한다.

각 경우마다 소모하는 에너지의 값이 양의 정수임을 증명할 수 있다.

제한

힌트