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: MEDIUM_HARD
Tags: Dynamic programming

Implementation
Skill types: Dynamic programming

Starter code:

Solutions:
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()


from sys import stdin, stdout
import sys
sys.setrecursionlimit(15000)
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))


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)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
n = int(input())
l = [int(x) - 1 for x in input().split()]
dp = [0] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
	dp[i] -= dp[l[i - 1]]
	dp[i] += 2 * dp[i - 1] + 2
print(dp[-1] % 1000000007)


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)


import sys
input = sys.stdin.readline
n = int(input())
z = list(map(int, input().split()))
pri = 10 ** 9 + 7
dp = [0 for i in range(len(z))]
su = [0 for i in range(len(z))]
dp[0] = 1
for i in range(len(z)):
	if z[i] == i + 1:
		if i == 0:
			su[i] = 2
		else:
			su[i] = su[i - 1] + 2
		dp[i] = 2
	else:
		total = 0
		for j in range(z[i] - 1, i):
			total += dp[j]
		su[i] = su[i - 1] + total + 2
		dp[i] = total + 2
		dp[i] %= pri
		su[i] %= pri
print(su[-1])


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


t = 1
mod = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0 for i in range(n + 1)]
	dp[0] = 2
	parity = [0] * (n + 1)
	parity[0] = 0
	for i in range(1, n):
		for j in range(l[i] - 1, i):
			dp[i] = (dp[i] % mod + dp[j] % mod) % mod
		dp[i] = (dp[i] % mod + 2) % mod
	suma = 0
	for i in range(n):
		suma = (suma % mod + dp[i] % mod) % mod
	print(suma)


n = int(input())
jmp = list(map(lambda x: x - 1, 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 os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def main():
	n = int(input())
	p = [0] + list(map(int, input().split()))
	dp = [0] * (n + 1)
	ans = 0
	for i in range(1, n + 1):
		ans += (ans - dp[p[i] - 1] + 1 + mod) % mod
		dp[i] = ans
	print((ans << 1) % mod)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
a = list(map(int, input().split()))
values = [0 for k in range(n)]
for k in range(n):
	back = a[k]
	if a[k] == k + 1:
		values[k] = 2
	else:
		values[k] += 2
		for t in range(a[k] - 1, k):
			values[k] += values[t]
		values[k] %= int(1000000000.0 + 7)
print(int(sum(values) % (1000000000.0 + 7)))


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


n = int(input())
p = list(map(int, input().split()))
m = int(1000000000.0 + 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])


n = int(input())
p = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [0] * (n + 1)
cum_dp = [0] * (n + 1)
for i in range(n):
	dp[i + 1] = (1 + cum_dp[i] - cum_dp[p[i] - 1]) % mod
	cum_dp[i + 1] = (cum_dp[i] + dp[i + 1] + 1) % mod
print(cum_dp[n])


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])


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])


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])


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)


n = int(input())
p = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[1] = 2
for i in range(2, n + 1):
	c = 0
	for j in range(p[i - 1], i):
		c += dp[j]
	dp[i] = c + 2
print(sum(dp) % (10 ** 9 + 7))


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)


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())
m = list(map(int, input().split()))
c = [0] * n
for i in range(n):
	c[i] = 2
	for j in range(m[i] - 1, i):
		c[i] += c[j]
mod = 10 ** 9 + 7
print(sum(c) % mod)


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)


n = int(input())
mod = int(1000000000.0 + 7)
dp = [0]
[dp.append((dp[-1] * 2 - dp[int(i) - 1] + 2) % mod) for i in input().split()]
print(dp[-1])


from __future__ import division, print_function
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
from collections import defaultdict
n = int(input())
l = list(map(int, input().split()))
l1 = [[0, 0] for i in range(n)]
ans = 0
d = defaultdict(int)
m = 10 ** 9 + 7

@bootstrap
def f(x):
	global n, ans, m
	d[x] += 1
	if d[x] == 2 and x != n:
		l1[x][1] = ans
	if d[x] == 1 and x != n:
		l1[x][0] = ans
	if x == n:
		yield 1
	if d[x] > 2:
		if d[x] % 2:
			ans += l1[x][1] - l1[x][0] + 1
			ans %= m
			d[x] += 1
			yield f(x + 1)
		else:
			ans += 1
			ans %= m
			yield f(x + 1)
	elif d[x] % 2:
		if d[l[x] - 1] > 1 and d[l[x] - 1] % 2 == 0:
			d[l[x] - 1] += 2
			ans += l1[l[x] - 1][1] - l1[l[x] - 1][0] + 2
			ans %= m
			yield f(l[x])
		elif d[l[x] - 1] > 1 and d[l[x] - 1] % 2:
			d[l[x] - 1] += 1
			ans += 2
			ans %= m
			yield f(l[x])
		else:
			ans += 1
			ans %= m
			yield f(l[x] - 1)
	else:
		ans += 1
		ans %= m
		yield f(x + 1)
	yield
f(0)
print(ans)


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)


n = int(input())
p = list(map(int, input().split()))
dp = [0] * (n + 1)
w = 10 ** 9 + 7
j = 1
while j <= n:
	dp[j] = (2 * (1 + dp[j - 1]) - dp[p[j - 1] - 1]) % w
	j += 1
print(dp[n])


no_rooms = int(input())
links = [None] + [int(x) for x in input().split()]
paths = [0] * (no_rooms + 2)
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)


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


n = int(input())
p = list(map(int, input().split()))
q = [0] * (n + 1)
q[0] = 0
q[1] = 2
ans = 2
mod = 10 ** 9 + 7
for i in range(1, n):
	ans = (ans + q[i] - q[p[i] - 1] + 2) % mod
	q[i + 1] = ans
print(ans)


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(sum)


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
prev = [0] + gil()
dp = [0] * (n + 1)
dp[1] = 2
ans = 2
for i in range(2, n + 1):
	dp[i] = 2
	for j in range(prev[i], i):
		dp[i] += dp[j]
		if dp[i] >= mod:
			dp[i] % mod
	ans += dp[i]
	if ans >= mod:
		ans %= mod
print(ans)


(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)


n = int(input())
p = list(map(int, input().split(' ', n)[:n]))
a = [i + 1 for i in range(n)]
dp1 = [0] * (n + 1)
dp1[1] = 2
dp2 = [0] * (n + 1)
dp2[1] = 2
mod = 10 ** 9 + 7
for i in range(2, n + 1):
	k = p[i - 1]
	an = 2
	for j in range(k, i):
		an += dp2[j] % mod
	dp2[i] = an % mod
	dp1[i] = dp2[i] + dp1[i - 1]
	dp1[i] %= mod
print(dp1[n])


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = x
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
n = I()
s = lint()
dp = [0] * (n + 1)
for i in range(1, n + 1):
	dp[i] = 2 * dp[i - 1] - dp[s[i - 1] - 1] + 2
print(dp[-1] % mod)


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


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