题目描述

最近龙骑士进入了一个迷宫，这个迷宫共有$\red{n+1}$个房间，编号从$\red{1...n+1}$。

现在龙骑士在第$\red{1}$个房间，需要到达第$\red{n+1}$个房间以出去。

房间$\red{i}$有两个前进的门（来时的门不算），第一扇门通向第$\red{i+1}$个房间，第二扇门通向第$\red{p_i(1<=p_i<=i)}$房间。

为了不迷路，龙骑士每到达一个房间，就会给这个房间画一个标记，画完后如果这个房间的标记数为偶数个，他就会选择这个房间第一扇门前进，否则选择第二扇门前进。

现在你需要求龙骑士需要通过多少道门到达终点（即第$\red{n+1}$个房间。）

答案对$\red{10^9+7}$取模

输入格式

第一行一个数$\red{n，}$

第二行$\red{n}$个整数$\red{p_i}$

输出格式

一个整数，即龙骑士需要通过多少道门到达终点

样例

输入样例

2
1 2

输出样例

4

提示

对于$\red{20\%}$的数据，满足$\red{n ≤}$ $\red{10}$

对于所有的数据，满足$\red{n ≤}$ $\red{10^3}$