페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7048
서브태스크

점프 점프 2초 1024MB

문제

문홍윤 코치는 점프의 달인이다.

오늘은 문홍윤 코치가 여러분의 앞에서 점프 묘기를 보여줄 것이다.

문홍윤 코치는 운동장에 준비된 N칸 짜리 매트 위에서 공중제비를 돌며 묘기를 보여줄 것이다.

문홍윤 코치는 1번 칸에 선 채로 묘기를 시작한다.

i번째 칸에서 문홍윤 코치가 점프를 하면 최소 1바퀴, 최대 x_i바퀴 까지 공중제비를 돌고 착지한다.

공중제비는 정확히 자연수 바퀴만 돈다. (잘 생각해보자. 1.5바퀴를 돌고 착지하면 머리부터 떨어진다.)

이 점프 시의 착지 위치는 공중제비 한 바퀴당 d_i칸만큼 멀어진다.

다시 말해 i번 칸에서 t바퀴의 공중제비를 돌고 떨어지면 i + t \times d_i번 칸으로 착지한다.

N번 칸 보다 뒤에 착지하는 점프는 불가능하다.

d_i = 0 이라면 그 칸에서는 점프할 수 없다는 의미이다.

홍윤 코치는 여러 번 점프를 이어 할 것이고 원한다면 아무 칸에서나 점프를 멈출 수 있다.

이렇게 몇 번 점프를 하고 멈추기까지를 하나의 묘기라고 부른다.

홍윤 코치가 기분이 안 좋으면 한 번의 점프도 보여주지 않고 끝낼 수도 있으며 이것도 묘기다.

두 묘기가 착지하는 칸의 집합이 같을 때 그 둘을 같은 묘기라고 부른다.

홍윤 코치는 몇 개의 서로 다른 묘기를 할 수 있을까?

너무 많으니 10^9+7로 나눈 나머지를 구해보자.


입력

첫 줄에 N이 주어진다.

이후 i번째 줄에는 d_i, x_i가 차례로 들어온다.

<제한>

  • 1\le N \le 10^5

  • 0\le d_i \le 10^9

  • 0\le x_i \le 10^9


출력

문홍윤 코치가 보여줄 수 있는 서로 다른 묘기의 가지수를 10^9+7로 나눈 나머지를 출력하라.


부분문제

번호 점수 조건
#18점

N \le 15

#213점

N \le 10^4

#316점

모든 i에 대해 d_i = 1

#434점

모든 i에 대해 x_i = 10^9

#529점

추가적인 조건이 없다.


예제1

입력
5
13
21
13
010
35
출력
7

태그


출처

BOI 2024 C번

역링크