← 返回题目列表

Codeforces · 407/B

B. 长路

中文机器翻译题面 查看原题

有一天,小瓦夏发现自己身处一个由 (n + 1) 个房间组成的迷宫,房间编号从 1 到 (n + 1)。最初,Vasya 位于第一个房间,要离开迷宫,他需要到达第 (n + 1) 个房间。

迷宫的组织方式如下。迷宫的每个房间都有两个单向门户。让我们考虑房间号 i (1 ≤ i ≤ n),有人可以使用第一个传送门从它移动到房间号 (i + 1),也有人可以使用第二个传送门从它移动到房间号 pi,其中 1 ≤ pi ≤ i。

为了不迷路,Vasya决定采取以下行动。

- 每次瓦夏进入某个房间时,他都会在天花板上画一个十字架。最初,瓦夏在 1 号房间的天花板上画了一个十字架。
- 假设 Vasya 在 i 号房间并且已经在天花板上画了一个十字架。然后,如果天花板现在包含奇数个十字架,则 Vasya 使用第二个门户(通向房间 pi),否则 Vasya 使用第一个门户。

帮助 Vasya 确定他最终需要使用传送门到达房间 (n + 1) 的次数。

输入

第一行包含整数 n (1 ≤ n ≤ 103) — 房间数。第二行包含 n 个整数 pi (1 ≤ pi ≤ i)。每个 pi 表示某人可以到达的房间号,如果他使用第 i 个房间中的第二个入口。

输出

打印一个数字——男孩走出迷宫所需的传送门移动次数。由于数字可能相当大,因此将其打印为对 1000000007 (109 + 7) 取模。

示例

输入 #1

2
1 2

输出 #1

4

输入 #2

4
1 1 2 3

输出 #2

20

输入 #3

5
1 1 1 1 1

输出 #3

62