Corridor

Time limit1sMemory limit2048 MB

Summary

Given N corridor segments with one-use teleporters that send David back to earlier segments, find his total walking time to exit, modulo 10^9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Statement

David wants to leave a secret science laboratory. He is at the far end of a corridor from the exit, so he has to walk the entire length of the corridor.

The corridor has $N$ segments. Some segments contain a teleporter.

Each teleporter sends whatever enters it to a fixed target segment. The target is always farther from the exit than the teleporter, so it is closer to David's starting point. Each teleporter can be switched on or off.

When David enters a segment with a switched-on teleporter, whether by walking or by teleportation, he is teleported to the target segment, and that teleporter switches off. When he enters a segment whose teleporter is off, he is not teleported, and the teleporter switches on.

All teleporters are on at the start.

Find how long it takes David to leave the laboratory.

Walking from one segment to the next takes one second. Teleportation is instantaneous. David always walks toward the exit. Leaving from the last segment also takes one second.

Input

The first line contains one integer $N$ ( $1 \le N \le 100\,000$ ), the number of segments.

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ( $1 \le A_i \le i$ ), the teleporter targets. If $A_i = i$ , segment $i$ is empty. Otherwise, segment $i$ has a teleporter that sends David to segment $A_i$ .

David starts at segment 1.

Output

Print David's time to exit the laboratory, modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
5
1 2 2 1 5
```
Expected output
```
10
```
Example 2
Input
```
3
1 1 2
```
Expected output
```
6
```
Example 3
Input
```
5
1 1 1 1 1
```
Expected output
```
31
```