20134번 - 소가 연세로를 건너간 이유

소가 왜 길을 건너는지에 대한 문제는 유명한 문제로, 농부 존의 소들이 길을 자주 건넌다는 것은 잘 알려진 사실이다. 그래서 존의 소들이 연세대학교에 와서 연세로를 건너려고 한다.

연세로 양쪽에 동서로 목초지가 평행하게 일렬로 1번부터 N번까지 있다. 서쪽의 i번 목초지에는 l_i번 소를, 동쪽의 i번 목초지에는 r_i번 소를 방목한다. 2017년 백금색의 길에 있는 목초지처럼 종별로 목초지 구조가 너무 달라서 한 목초지에는 정해진 종의 소만 방목할 수 있다. 즉, i번 목초지에는 i번 소만 방목할 수 있다. 소가 자신의 종을 방목하는 반대편의 목초지로 이동할 때 연세로를 건넌다고 한다.

목초지의 순서가 뒤죽박죽이어서, a 종의 소와 b 종의 소가 건너는 길이 겹칠 수도 있다. 존이 목초지 건설에 주의를 기울이지 않은 탓이다. 이때 (a, b)를 "가로지르는 쌍"이라고 하자.

존은 가로지르는 쌍의 수를 계산하기에 앞서, 2017년 백금색의 길을 건널 때랑 조금 다른 방법을 고안했다. 0 ≤ k₁, k₂ < N인 정수 k₁, k₂에 대해서 한쪽 목초지에서 맨 뒤에 있는 목초지 k₁개를 맨 앞으로 옮기고, 다른 쪽 목초지에서 맨 뒤에 있는 k₂개를 맨 앞으로 순서 변경 없이 옮기는 것이다. 하지만, 존은 k₁과 k₂를 무엇으로 할지 아직 정하지 않았다.

모든 0 ≤ k₁, k₂ < N에 대해서 가로지르는 쌍의 개수의 합을 1,000,000,009로 나눈 나머지를 구하여라.

다음과 같이 입력이 주어진다.

가로지르는 쌍의 개수의 합을 1,000,000,009로 나눈 나머지를 출력한다.

• 1 ≤ N ≤ 1,000,000.
• 1 ≤ l_i, r_i ≤ N. (1 ≤ i ≤ N). 각각 i 번째 서쪽 목초지 번호와 동쪽 목초지 번호를 의미한다.
• l_i ≠ l_j, r_i ≠ r_j. (1 ≤ i < j ≤ N).
• 입력에 주어진 수들은 전부 정수다.