Corridor

문제

David wants to exit a secret science laboratory. He is in a corridor on the opposite end from the exit, so he will have to walk along the entire length of the corridor.

It would be straightforward to leave, but some teleporters are being tested in the corridor. The corridor consists of $NN$ segments. Some segments contain a teleporter.

Each teleporter is configured to teleport stuff into a particular target segment. The target segment is always further from the exit (and thus closer to David's starting position) than the teleporter itself. Also each teleporter may be switched on or off.

When David enters (either walks or is teleported into) a segment with a turned-on teleporter, he is teleported into the target segment, and the teleporter turns off. When David enters a segment with a turned-off teleporter, he is not teleported, but the teleporter turns on.

All teleporters are turned on initially.

Find how long it will take David to leave the laboratory.

It takes one second for David to walk from one segment to the next. Teleportation is instantaneous. David will always walk towards the exit. Exiting the laboratory from the last segment of the corridor also takes one second.

Since the answer may be very large, output the remainder when David's total walking time (in seconds) is divided by ${10}^9+710^9\; +\; 7$.

입력

The first line contains one integer $NN$ ($1\le N\le 1000001\; \backslash le\; N\; \backslash le\; 100\backslash ,000$), the number of segments the corridor consists of.

The second line contains $NN$ integers $A_1,A_2,\dots ,A_{N}A\_1,\; A\_2,\; \backslash ldots,\; A\_N$ ($1\le A_i\le i1\; \backslash le\; A\_i\; \backslash le\; i$) denoting the teleporter targets. If $A_i=iA\_i\; =\; i$, then the $ii$-th segment is empty. Otherwise the $ii$-th segment contains a teleporter which teleports stuff into the $A_{i}A\_i$-th segment.

David starts at the $11$-st segment.

출력

Output one integer, David's time to exit the lab, modulo ${10}^9+710^9\; +\; 7$.

5
1 2 2 1 5

10

3
1 1 2

6

5
1 1 1 1 1

31