공의 합집합

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

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

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

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

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