시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 1024 MB 49 16 9 34.615%

문제

3차원 좌표공간에 n개의 공(ball)이 있다. 이 중 i (1 ≤ in)번째 공은 겉표면이 중심이 (xi, 0, 0)이고 반지름은 ri인 구 형태이며, 이 공이 차지하는 영역은 Si = {(x, y, z) ∈ ℝ3 : (x - xi)2 + y2 + z2ri2}이다.

모든 공의 합집합 S1S2 ∪ ··· ∪ Sn의 부피를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 공의 개수 n (1 ≤ n ≤ 300,000)이 주어진다.

다음 n개 줄에는 공의 정보가 한 줄에 하나씩 주어지는데, 이 중 i (1 ≤ in)번째 줄에는 두 개의 정수 xi (0 ≤ xi ≤ 106)와 ri (1 ≤ ri ≤ 106)가 공백 하나를 사이로 두고 주어진다.

출력

모든 공의 합집합 S1S2 ∪ ··· ∪ Sn의 부피는 pq π (단, pq는 서로소인 두 자연수)로 나타낼 수 있다. 이때, 첫 번째 줄에 Vqp (mod 109 + 7)을 만족하는 0 이상 109 + 6 이하의 정수 V를 출력하라. 입력 제약 조건을 만족하는 모든 입력에서 이러한 V가 유일하게 존재함을 증명할 수 있다.

예제 입력 1

1
1 4

예제 출력 1

333333421

반지름이 4인 공의 부피는 43 · 43· π = 2563 π이다. V ⋅ 3 ≡ 256 (mod 109+ 7)의 해를 구하면 V ≡ 333,333,421 (mod 109+ 7)이다.

예제 입력 2

2
3 4
6 3

예제 출력 2

100

그림은 아래와 같으며, 합집합의 부피는 100π이다.

sphere