시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB4781219431.023%

문제

서울에는 한강이라는 이름의 강이 동서 방향으로 흐른다. 북쪽 강변에는 서쪽에서 동쪽으로 가는 방향으로 1 부터 N 까지 번호가 붙은 N개의 보트 학교가 있다. 한 학교의 보트들은 색이 같고, 따라서 서로 구별할 수 없다. 다른 학교의 보트들은 반드시 색이 다르고, 따라서 항상 구별이 된다. i번 학교는 축제에 보트를 하나도 내보내지 않을 수 있다. 만약 i번 학교가 축제에 보트를 내보내기로 했다면 ai개 부터 bi개 사이(양 끝 포함)의 보트를 내보낼 수 있다. (ai ≤ bi)

한가지 중요한 조건은, i번 학교가 보트를 내보내기로 한 경우에는 i보다 번호가 작은 그 어떠한 학교가 내보낸 보트 수 보다 많은 수의 보트를 내보내야 한다는 것이다. (보트를 내보낸 i보다 번호가 작은 학교가 존재하는 경우에 적용된다.)

모든 학교의 ai와 bi 값을 입력으로 받아서 학교들이 보트를 내보낼 수 있는 모든 가능한 경우의 수를 계산하는 프로그램을 작성하라. 단, 최소한 한 학교는 보트를 내보내는 경우들만 계산에 포함된다.

입력

입력의 첫 줄에는 학교의 수를 나타내는 자연수 N (1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄 중 i번째에는 ai 와 bi가 주어진다. (1 ≤ ai ≤ bi ≤ 109)

출력

출력은 단 한줄이며, 학교들이 보트를 내보낼 수 있는 방법의 경우의 수를 1,000,000,007로 나눈 나머지를 출력하여야 한다.

예제 입력 1

2
1 2
2 3

예제 출력 1

7

힌트

하나의 학교만 보트를 내보내는 방법은 모두 4가지가 있으며,

두 학교가 모두 보트를 내보내는 방법은 3가지가 있어서, 답은 7이다

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2016 1번