Long Path

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 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³) — 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⁹ + 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

Solution:

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

const int md = 1000000007;
const int N = 1234567;

int p[N], f[N];

int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", p + i);
  f[1] = 2;
  for (int i = 2; i <= n; i++) {
    f[i] = 2;
    for (int k = p[i]; k < i; k++) {
      f[i] += f[k];
      if (f[i] >= md) f[i] -= md;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans += f[i];
    if (ans >= md) ans -= md;
}
printf("%d\n", ans);
return 0;
}