Long Path

题意翻译

有个人进入一个迷宫,这个迷宫共有n+1个房间,编号从1~n+1,ta现在在第1个房间,需要到达第n+1个房间以出去。房间i有两个前进的门(来时的门不算),第一扇门通向第i+1个房间,第二扇门通向第pi(1<=pi<=i)房间,为了不迷路,这个人每到达一个房间,就会给这个房间画一个标记,画完后如果这个房间的标记数为偶数个,ta就会选择这个房间第一扇门前进,否则选择第二扇门前进。 求这个人需要通过多少道门到达终点(即第n+1个房间),答案对1000000007取模 输入:第一行一个数n,第二行n个整数pi,n和pi的含义见题目翻译 输出:一个整数,即这个人需要通过多少道门到达终点 感谢@守望 提供的翻译

题目描述

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.

输入输出格式

输入格式


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.

输出格式


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

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

4

输入样例 #2

4
1 1 2 3

输出样例 #2

20

输入样例 #3

5
1 1 1 1 1

输出样例 #3

62