Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 04:05:06 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|