APIO 2016 Republic of Korea- Boat > 문제은행 : 정보올림피아드&알고리즘




3007 : Boat

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
6 회   
시도횟수
23 회   

문제

서울에는 한강이라는 이름의 강이 동서 방향으로 흐른다. 

북쪽 강변에는 서쪽에서 동쪽으로 가는방향으로 1 부터 N 까지 번호가 붙은 N 개의 보트 학교가 있다. 

한 학교의 보트들은 색이 같고, 따라서 서로 구별할 수 없다. 다른 학교의 보트들은 반드시 색이 다르고, 따라서 항상 구별이 된다.

 

 i 번 학교는 축제에 보트를 하나도 내보내지 않을 수 있다.

만약 i 번 학교가 축제에 보트를 내보내기로 했다면 ai 개 부터 bi 개 사이(양 끝 포함)의 보트를 내보낼 수 있다. (ai ≤ bi)


한가지 중요한 조건은, i 번 학교가 보트를 내보내기로 한 경우에는 i 보다 번호가 작은 그 어떠한 학교가 

내보낸 보트 수 보다 많은 수의 보트를 내보내야 한다는 것이다. (보트를 내보낸 i 보다 번호가 작은 학교가 존재하는 경우에 적용된다.)

 

Task
모든 학교의 ai 와 bi 값을 입력으로 받아서 학교들이 보트를 내보낼 수 있는 모든 가능한 경우의 수를 계산하는 프로그램을 작성하라. 

단, 최소한 한 학교는 보트를 내보내는 경우들만 계산에 포함된다.

 

Scoring
Subtask 1 (9 점): 1≤N≤500 이고, 모든 1≤i≤N 에 대해 ai=bi.
Subtask 2 (22 점): 1≤N≤500 이고 ∑1≤i≤N (b1-a1)≤10^6.
Subtask 3 (27 점): 1≤N≤100.
Subtask 4 (42 점): 1≤N≤500.


입력형식

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

출력형식

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

입력 예

2
1 2
2 3

출력 예

7

Hint!

하나의 학교만 보트를 내보내는 방법은 모두 4가지가 있으며, 두 학교가 모두 보트를 내보내는 방법은 3가지가 있어서, 답은 7이다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP