题目描述

学校里有一条由 $n$ 个房间首尾排成的长廊，房间编号为 $1,2,\dots,n$。小 A 从房间 $1$ 出发，目标是到达房间 $n$。

对于每个房间 $i$（$1 \le i < n$），都安装了一组弹簧装置。若当前站在房间 $i$，则他可以一跃最多跳$a_i$ 步，也就是可以跳到下面任意一个房间：

其中 $a_i$ 由输入给出；若 $a_i=0$，则表示从房间 $i$ 无法继续前进。

请你计算：从房间 $1$ 到房间 $n$ 一共有多少种不同的走法。由于答案可能很大，请对 $10^9+7$ 取模后输出。

输入格式

第一行输入一个整数 $n$。
第二行输入 $n-1$ 个整数 $a_1,a_2,\dots,a_{n-1}$。
数据范围：

• $1 \le n \le 3000$
• $0 \le a_i \le 3000$
• $\sum_{i=1}^{n-1} a_i \le 20000$

输出格式

输出一行，一个整数，表示不同走法数对 $10^9+7$ 取模后的结果。

6
2 3 1 2 1

7

Hint

样例解释： 所有合法走法分别是：

1 -> 2 -> 3 -> 4 -> 5 -> 6
1 -> 2 -> 3 -> 4 -> 6
1 -> 2 -> 4 -> 5 -> 6
1 -> 2 -> 4 -> 6
1 -> 2 -> 5 -> 6
1 -> 3 -> 4 -> 5 -> 6
1 -> 3 -> 4 -> 6

因此答案为 $7$。