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^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

Difficulty: competition

Starter code:

Solutions:
n,a= int(input()),list(map(int,input().split()))
f,m= [0]*(n+1),10**9+7
for i in range(n):
	if a[i]==i+1:
		f[i+1]=f[i]+2
	else:
		f[i+1]=(2+f[i]*2-f[a[i]-1])%m
print(f[n]%m)


Mod=1000000007
n=int(input())
p=list( map(int, input().split()) )
s=[0,2]
for i in range(2,n+1):
    s.append( ( 2*s[i-1]-s[p[i-1]-1] + 2 + Mod ) % Mod )
print(s[n])


import sys
MOD = 10**9+7
N = int(sys.stdin.readline())
bs = [int(b)-1 for b in sys.stdin.readline().split()]
fs = [0]
for i in range(1,N+1):
    f = 2*fs[i-1] + 2 - fs[bs[i-1]]
    fs.append(f % MOD)
print(fs[-1])


n = int(input())
q, p = 1000000007, [0] + list(map(int, input().split()))
s, d = 0, [0] * (n + 1)
for i in range(1, n + 1):
    d[i] = (sum(d[p[i]: i]) + 2) % q
    s += d[i]
print(s % q)

#!/usr/bin/env python3

n = int(input())
jmp = list([x - 1 for x in list(map(int, input().split()))])

cache = { }

def DP(i,j):
    if (i,j) not in cache:
        if i == j:
            cache[i,j] = 0
        elif i + 1 == j:
            cache[i,j] = DP(jmp[i], i) + 2
        else:
            cache[i,j] = sum(DP(k, k+1) for k in range(i,j))

    return cache[i,j]

print(DP(0, n) % (10**9 + 7))


import sys
MOD = 10 ** 9 + 7
N = int(input())
bs = [int(b) - 1 for b in input().split()]
fs = [0]
for i in range(1,N+1):
    f = 2 * fs[i - 1] + 2 - fs[bs[i - 1]]
    fs.append(f % MOD)
print(fs[-1])

#! python3
numRooms = int(input())
links = [0]+[int(x) for x in input().split()]
portalPaths = [0]*(numRooms+2)
for index in range(1, numRooms + 1):
	portalPaths[index + 1] = (2*portalPaths[index] - portalPaths[links[index]] + 2) % 1000000007
print(portalPaths[numRooms+1] % 1000000007)

# print(numRooms)
# print(links)


# This implementation is too slow
# numRooms = int(input())
# links = [-1]+[int(x) for x in input().split()]
# crosses = [0]+[0]*(numRooms + 1)
# current = 1
# while current <= numRooms:
# 	if crosses[current] % 2 == 0:
# 		crosses[current] += 1
# 		print(current, crosses[current], "portal")
# 		current = links[current]
# 	else:
# 		crosses[current] += 1
# 		print(current, crosses[current], "plus 1")
# 		current += 1

# print(sum(crosses) % 1000000007)


import sys

def solve():
    mod = 1000 * 1000 * 1000 + 7
    n, = rv()
    a, = rl(1)
    mem = [0] * n
    # mem[0] = 1
    timesofar = 0
    for i in range(n):
        ariveat = a[i] - 1
        moresum = 0
        for j in range(ariveat, i):
            moresum += mem[j]
        mem[i] = moresum + 1
        timesofar += moresum + 1
        timesofar %= mod
    print((2 * timesofar) % mod)


def rv(): return list(map(int, input().split()))
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()




import sys

def solve():
    mod = 1000 * 1000 * 1000 + 7
    n, = rv()
    a, = rl(1)
    a.append(0)
    mem = [0] * (n + 1)
    timesofar = 0
    for i in range(n + 1):
        ariveat = a[i] - 1
        moresum = 0
        for j in range(ariveat, i):
            moresum += mem[j]
        mem[i] = moresum + 1
        timesofar += moresum + 1
        timesofar %= mod
    print(timesofar - 1)


def rv(): return list(map(int, input().split()))
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()




import sys

def solve():
    mod = 1000 * 1000 * 1000 + 7
    n, = rv()
    a, = rl(1)
    mem = [0] * n
    timesofar = 0
    for i in range(n):
        ariveat = a[i] - 1
        moresum = 0
        for j in range(ariveat, i):
            moresum += mem[j]
        mem[i] = moresum + 2
        timesofar += moresum + 2
        timesofar %= mod
    print(timesofar)


def rv(): return list(map(int, input().split()))
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()




n = int(input())
pt = [0] + list(map(int, input().split(" ")))
dp = [0 for i in range(1005)]
MOD = int(1e9+7)
for i in range(1, n+1):
    dp[i+1] = (2*dp[i] + 2 - dp[pt[i]])%MOD
print(dp[n+1]%MOD)


no_rooms = int(input())
links = [None] + [int(x) for x in input().split()]
paths = [0] * (no_rooms + 2) # last is total

for i in range(1, no_rooms + 1):
	paths[i + 1] = (2 * paths[i] - paths[links[i]] + 2) % 1000000007

print(paths[no_rooms + 1] % 1000000007)

n = int(input())
p = list(map(int, input().split()))
m = int(1e9 + 7)

dp = [0] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    dp[i] = (2 * dp[i - 1] - dp[p[i - 1] - 1] + 2) % m

print(dp[n])


input()
dp = [0] 
[dp.append((2 * dp[-1] + 2 - dp[u - 1]) % 1000000007) for u in map(int, input().split())]
print (dp[-1])

input()
dp = [0] 
[dp.append((2 * dp[-1] + 2 - dp[u - 1]) % 1000000007) for u in map(int, input().split())]
print (dp[-1])

z = int(input())
l = [None] + [int(x) for x in input().split()]
pt = [0] * (z + 2)

for i in range(1, z + 1):
	pt[i + 1] = (2 * pt[i] - pt[l[i]] + 2) % 1000000007

print(pt[z + 1] % 1000000007) 

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n+1)]
for i in range(n+1):
    if i > 0 : dp[i] = (2*dp[i-1]+2-dp[a[i-1]-1])%1000000007
print((dp[n]+1000000007)%1000000007)

Mod=1000000007
n=int(input())
p=list( map(int, input().split()) )
s=[0,2]
for i in range(2,n+1):
    s.append( ( 2*s[i-1]-s[p[i-1]-1] + 2 + Mod ) % Mod )
print(s[n])




# Made By Mostafa_Khaled


MOD = 10 ** 9 + 7

n = int(input())
p = [0] + list(map(int, input().split()))

ways = [0 for i in range(n + 2)]


for i in range(1, n + 1):
    ways[i] = 1
    for j in range(p[i], i):
        ways[i] += ways[j] + 1
        ways[i] %= MOD

print((sum(ways) + n) % MOD)


n = int(input())
ls = list(map(int,input().split()))
ls1 = list([0]*n)
sum = 2
ls1[0] = 2 
mod = 1000000007
for i in range(1,n):
    ls1[i] = 2
    k = ls[i]
    k -= 1
    for j in range(k,i):
        ls1[i] += ls1[j]
        ls1[i] %= mod
    sum += ls1[i]
    sum %= mod
   # print(ls1[i])
print(sum)

R = lambda: map(int, input().split())
n = int(input())
mod = 1000000007
arr = [x - 1 for x in R()]
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[0] = sdp[0] = 2
for i in range(1, len(arr)):
    dp[i] = (2 + sdp[i - 1] - sdp[arr[i] - 1]) % mod
    sdp[i] = (sdp[i - 1] + dp[i]) % mod
print(sdp[n - 1])

'''input
4
1 1 2 3
'''
from sys import stdin, stdout
import sys


sys.setrecursionlimit(15000)


# main starts
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
dp = [-1] * (n + 1)
dp[1] = 2
mod = 10 ** 9 + 7
for i in range(2, n + 1):
	dp[i] = (sum(dp[arr[i - 1] : i]) + 2) % mod
print(sum(dp[1:]) % (10 ** 9 + 7))


n=int(input())
l=list(map(int,input().split()))
L=[[0,1]]
for i in range(1,n) :
    v=L[i-1][1]+1
    L.append([v,0])
    y=L[l[i]-1][0]
    L[i][1]=v+v-y+1
    
print((L[-1][1]+1)%1000000007)


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/8/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(N, A):
    MOD = 10**9 + 7
    dp = [0 for _ in range(N+1)]
    for i in range(N):
        dp[i+1] = 2 * dp[i] + 2 - dp[A[i]]
        dp[i+1] %= MOD
    return dp[N]
    

N = int(input())
A = [int(x)-1 for x in input().split()]
print(solve(N, A))

n = int(input())

mod = 10**9 + 7

a = [int(_) - 1 for _ in input().split()]
b = [0]

for i in range(1, n + 1):
	v = 2 * b[i - 1] + 2 - b[a[i - 1]]
	b.append(v % mod)
print(b[-1])