有一天,小瓦夏发现自己身处一个由 (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