스프링클러

농부 존은 넓은 밭을 가지고 있는데, 그 일부에 단옥수수를 심으려고 생각 중이다. 밭을 측량해 본 결과, 농부 존의 밭은 \((N-1) \times (N-1)\) 크기의 정사각형을 이룬다는 것을 알았다. 남서쪽 모서리는 좌표 \((0,0)\)에 있고, 북동쪽 모서리는 \((N-1,N-1)\)에 있다.

어떤 정수 좌표들에는 물과 비료를 모두 뿌리는 양방향 헤드 스프링클러가 있다. 좌표 \((i,j)\)에 있는 양방향 헤드 스프링클러는 그 지점의 북쪽과 동쪽에 있는 밭 부분에 물을 뿌리고, 남쪽과 서쪽에 있는 밭 부분에 비료를 뿌린다. 형식적으로, 이 스프링클러는 \(N \geq x \geq i\)이고 \(N \geq y \geq j\)인 모든 실수 좌표 \((x,y)\)에 물을 뿌리고, \(0 \leq x \leq i\)이고 \(0 \leq y \leq j\)인 모든 실수 좌표 \((x,y)\)에 비료를 뿌린다.

농부 존은 모서리 좌표가 정수인, 축에 평행한 어떤 직사각형에 단옥수수를 심고 싶다. 하지만 단옥수수가 자라려면 직사각형 안의 모든 점이 양방향 헤드 스프링클러에 의해 물과 비료를 모두 받아야 한다. 그리고 당연히 직사각형의 넓이는 양수여야 한다. 그렇지 않으면 농부 존은 그 안에서 옥수수를 전혀 기를 수 없을 것이다!

농부 존이 단옥수수를 기를 수 있는, 넓이가 양수인 직사각형의 개수를 구하도록 도와주자. 이 수는 매우 클 수 있으므로, 이 수를 \(10^9 + 7\)로 나눈 나머지를 출력한다.

출제자: Dhruv Rohatgi

출제자: Dhruv Rohatgi

입력의 첫째 줄에 밭의 크기를 나타내는 정수 \(N\)이 하나 주어진다 (\(1 \leq N \leq 10^5\)).

다음 \(N\)개의 줄에는 각각 공백으로 구분된 정수 두 개가 주어진다. 이 정수들이 \(i\)와 \(j\)라면 (\(0 \leq i,j \leq N-1\)), \((i,j)\)에 위치한 스프링클러를 나타낸다.

각 열에 정확히 하나의 스프링클러가 있고 각 행에도 정확히 하나의 스프링클러가 있음이 보장된다. 즉, 어떤 두 스프링클러도 같은 \(x\)좌표를 갖지 않고, 어떤 두 스프링클러도 같은 \(y\)좌표를 갖지 않는다.

물과 비료를 모두 완전히 받는, 넓이가 양수인 직사각형의 개수를 \(10^9 + 7\)로 나눈 나머지를 나타내는 정수 하나를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > January > Platinum