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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

점프 점프 timer 2s memory 1024MB

점프 점프 2s 1024MB