17378번 - 공의 합집합

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

모든 공의 합집합 S₁ ∪ S₂ ∪ ··· ∪ S_n의 부피를 구하는 프로그램을 작성하라.

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

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

모든 공의 합집합 S₁ ∪ S₂ ∪ ··· ∪ S_n의 부피는 ^p⁄_q π (단, p와 q는 서로소인 두 자연수)로 나타낼 수 있다. 이때, 첫 번째 줄에 V ⋅ q ≡ p (mod 10⁹ + 7)을 만족하는 0 이상 10⁹ + 6 이하의 정수 V를 출력하라. 입력 제약 조건을 만족하는 모든 입력에서 이러한 V가 유일하게 존재함을 증명할 수 있다.