Con đường dài

Một mê cung gồm $n+1$ căn phòng đánh số từ $1$ đến $n+1$. Ban đầu một người đứng ở phòng $1$ và muốn ra khỏi mê cung bằng cách tới được phòng $n+1$.

Mỗi phòng $i$ (với $1\le i\le n$) có hai cổng dịch chuyển một chiều:

• Cổng thứ nhất đưa từ phòng $i$ sang phòng $i+1$.
• Cổng thứ hai đưa từ phòng $i$ sang phòng $p_i$, trong đó $1\le p_i\le i$.

Người này di chuyển theo quy tắc sau:

• Mỗi khi bước vào một phòng, anh ta vẽ thêm một dấu chéo lên trần phòng đó. Ban đầu anh ta vẽ một dấu chéo lên trần phòng $1$.
• Giả sử anh ta đang ở phòng $i$ và vừa vẽ dấu chéo. Nếu trần phòng hiện có một số lẻ dấu chéo thì anh ta dùng cổng thứ hai (tới phòng $p_i$), ngược lại (số chẵn) anh ta dùng cổng thứ nhất (tới phòng $i+1$).

Hãy xác định số lần anh ta cần sử dụng cổng để tới được phòng $n+1$.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$.

Dữ liệu ra

In ra một số nguyên duy nhất là số lần sử dụng cổng cần thiết. Do đáp số có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^3$
• $1\le p_i\le i$

Ví dụ