만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

궁금한 심사위원

시간 제한3초메모리 제한1024 MB

요약
각 팀이 마지막 제출 시각과 제출 시각의 합 중 하나를 패널티로 고를 때, 순위와 패널티가 같은 고정점의 총개수를 모든 경우에 대해 더한 값을 10^9+7로 나눈 나머지를 구합니다.
난이도

어려움10점 중 8점

유형
조합론, 누적 합, 수학
정답자
아직 제출이 없습니다

문제

경쟁 프로그래밍 대회에서는 제출 시간으로 동점을 가르는 방법이 여러 가지 있다. 이 대회는 정답 제출의 제출 시간을 모두 더한 값을 벌점으로 쓴다. 다른 대회는 팀의 마지막 정답 제출 시각을 벌점으로 쓴다.

심사위원으로서 고정점에 관심이 있다. 고정점은 스코어보드에서 팀의 순위가 벌점과 같은 위치다. 모든 팀이 모든 문제를 풀었으므로, 팀의 순위는 벌점이 엄격히 작은 팀의 수에 1을 더한 값이다.

각 팀에는 제출 시간의 합 ss와 마지막 제출 시각 ll이 있다. 문제가 두 개 이상이므로 모든 팀에서 l<sl < s가 성립한다. 제출 시간의 합은 팀의 수 nn을 넘지 않는다.

각 팀마다 두 가지 벌점 계산 방식 중 하나를 고른다. 어떤 선택에 대해 gg를 스코어보드의 고정점 개수라고 하자. 벌점을 고르는 2n2^n가지 방법 모두에 대해 gg의 총합을 구하라.

입력

첫 줄에 팀의 수 nn (2≤n≤2⋅1052 \leq n \leq 2\cdot10^5)이 주어진다.

이어지는 nn개의 줄에는 각각 정수 ll과 ss (1≤l<s≤n1 \leq l < s \leq n)가 주어진다. 한 팀의 마지막 제출 시각과 제출 시간의 합이다.

출력

벌점을 고르는 2n2^n가지 방법 모두에 대해 gg의 총합을 출력한다. 답이 매우 클 수 있으므로 소수 109+710^9+7로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

    입력
    3
    1 2
    2 3
    1 3
    
    예상 출력
    16
    
  2. 예제 2

    입력
    10
    1 6
    2 7
    3 8
    1 2
    5 9
    9 10
    1 10
    2 8
    3 4
    4 5
    
    예상 출력
    4752