No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Long Path

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne day, little Vasya found himself in a maze consisting of (*n* + 1) rooms, numbered from 1 to (*n* + 1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (*n* + 1)-th one.

The maze is organized as follows. Each room of the maze has two one-way portals. Let's consider room number *i* (1 ≤ *i* ≤ *n*), someone can use the first portal to move from it to room number (*i* + 1), also someone can use the second portal to move from it to room number *p*_{i}, where 1 ≤ *p*_{i} ≤ *i*.

In order not to get lost, Vasya decided to act as follows.

- Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1.
- Let's assume that Vasya is in room
*i*and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room*p*_{i}), otherwise Vasya uses the first portal.

Help Vasya determine the number of times he needs to use portals to get to room (*n* + 1) in the end.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{3}) — the number of rooms. The second line contains *n* integers *p*_{i} (1 ≤ *p*_{i} ≤ *i*). Each *p*_{i} denotes the number of the room, that someone can reach, if he will use the second portal in the *i*-th room.

Output

Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (10^{9} + 7).

Examples

Input

2

1 2

Output

4

Input

4

1 1 2 3

Output

20

Input

5

1 1 1 1 1

Output

62

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/06/2021 20:35:34 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|