http://codeforces.com/contest/407/problem/B

One 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 pi, where 1 ≤ pi ≤ 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 pi), 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 ≤ 103) — the number of rooms. The second line contains n integers pi (1 ≤ pi ≤ i). Each pi 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 (109 + 7).

题意：n个格子，每到达一个格子，首先在这个格子画一个十字架，然后，如果当前十字架个数为奇数，跳到p[i]（在i上或i左），偶数则到i+1，求到达n+1格子的步数。

思路：仔细想一下这个走的顺序，第一次到达i，这时i左边各个格子都是偶数，和没有走过（0）是等效的，从i到p[i],转化为了第一次到达p[i]，p[i]会和之前一样的方式，一样的步数到达i，此时又满足i左边各个格子都是偶数，并且i也是偶数，走到i+1。

并且他一定能走到终点，不存在到不了终点的情况。1一定能到2，2就算回到1，既然1能到2，到了2就一定能到3，3一定能到4......n一定能到n+1。

明显的一个线性dp模型：设d(i):第一次走到i的步数（都不需要分开设第一次第二次到达i 的步数）

d(i)=d(i-1)+d(i-1)-d(p[i-1])+1+1

取模容易搞错，用longlong好一些。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
#define mod 1000000007

int n,p[maxn],d[maxn];

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	d[1]=0;
	for(int i=2;i<=n+1;i++)d[i]=((d[i-1]+d[i-1]-d[p[i-1]]+1+1)%mod+mod)%mod;
	cout<<d[n+1]<<endl;
	return 0;
}