복도

시간 제한1초메모리 제한2048 MB

요약

N개의 구간과 한 번 작동한 뒤 꺼지는 순간이동 장치가 주어질 때, 다윗이 출구로 나가는 데 걸리는 시간을 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 누적 합
정답자: 아직 제출이 없습니다

문제

David는 비밀 과학 연구소에서 빠져나가려 한다. 그는 출구 반대편 끝의 복도에 있어서, 복도 전체 길이를 걸어가야 한다.

복도는 $N$ 개의 구간으로 이루어져 있으며, 일부 구간에는 순간이동 장치가 있다.

각 순간이동 장치는 정해진 목표 구간으로 사람을 보낸다. 목표 구간은 항상 장치가 있는 구간보다 출구에서 멀리 떨어져 있고, 따라서 David의 출발 지점에 더 가깝다. 각 장치는 켜거나 끌 수 있다.

David가 (걸어서든 순간이동으로든) 켜진 순간이동 장치가 있는 구간에 들어가면, 목표 구간으로 순간이동하고 그 장치는 꺼진다. 꺼진 장치가 있는 구간에 들어가면 순간이동은 일어나지 않고 장치가 켜진다.

처음에는 모든 장치가 켜져 있다.

David가 연구소를 빠져나가는 데 걸리는 시간을 구하라.

인접한 구간으로 걸어가는 데 1초가 걸린다. 순간이동은 시간이 걸리지 않는다. David는 항상 출구 방향으로 걷는다. 마지막 구간에서 나가는 데도 1초가 걸린다.

입력

첫째 줄에 구간의 개수 $N$ ( $1 \le N \le 100\,000$ )이 주어진다.

둘째 줄에는 순간이동 목표를 나타내는 정수 $A_1, A_2, \ldots, A_N$ ( $1 \le A_i \le i$ )이 주어진다. $A_i = i$ 이면 $i$ 번째 구간은 비어 있다. 그렇지 않으면 $i$ 번째 구간에 장치가 있으며, David를 $A_i$ 번째 구간으로 보낸다.

David는 1번째 구간에서 출발한다.

출력

연구소를 빠져나가는 데 걸리는 시간을 $10^9 + 7$ 로 나눈 나머지를 출력하라.

예제3

예제 1
입력
```
5
1 2 2 1 5
```
예상 출력
```
10
```
예제 2
입력
```
3
1 1 2
```
예상 출력
```
6
```
예제 3
입력
```
5
1 1 1 1 1
```
예상 출력
```
31
```