문제
서울에는 한강이라는 이름의 강이 동서 방향으로 흐른다.
북쪽 강변에는 서쪽에서 동쪽으로 가는방향으로 1 부터 N 까지 번호가 붙은 N 개의 보트 학교가 있다.
한 학교의 보트들은 색이 같고, 따라서 서로 구별할 수 없다. 다른 학교의 보트들은 반드시 색이 다르고, 따라서 항상 구별이 된다.
i 번 학교는 축제에 보트를 하나도 내보내지 않을 수 있다.
만약 i 번 학교가 축제에 보트를 내보내기로 했다면 ai 개 부터 bi 개 사이(양 끝 포함)의 보트를 내보낼 수 있다. (ai ≤ bi)
한가지 중요한 조건은, i 번 학교가 보트를 내보내기로 한 경우에는 i 보다 번호가 작은 그 어떠한 학교가
내보낸 보트 수 보다 많은 수의 보트를 내보내야 한다는 것이다. (보트를 내보낸 i 보다 번호가 작은 학교가 존재하는 경우에 적용된다.)
Task
모든 학교의 ai 와 bi 값을 입력으로 받아서 학교들이 보트를 내보낼 수 있는 모든 가능한 경우의 수를 계산하는 프로그램을 작성하라.
단, 최소한 한 학교는 보트를 내보내는 경우들만 계산에 포함된다.
입력
입력의 첫 줄에는 학교의 수를 나타내는 자연수 N 이 주어진다.
다음 N 개의 줄 중 i 번째에는 ai 와 bi 가 주어진다. (1≤ai≤bi≤109)
출력
출력은 단 한줄이며, 학교들이 보트를 내보낼 수 있는 방법의 경우의 수를 1,000,000,007 로 나눈나머지를 출력하여야 한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 9점 | 1≤N≤500 이고, 모든 1≤i≤N 에 대해 ai=bi. |
| #2 | 22점 | 1≤N≤500 이고 |
| #3 | 27점 | 1≤N≤100. |
| #4 | 42점 | 1≤N≤500. |
예제
2
1 2
2 3
7
하나의 학교만 보트를 내보내는 방법은 모두 4가지가 있으며, 두 학교가 모두 보트를 내보내는 방법은 3가지가 있어서, 답은 7이다.
로그인해야 코드를 작성할 수 있어요.