“Chetree” 是一种有根标号树，其中每个顶点的子节点顺序是固定的。我们可以通过改变某些顶点的子节点顺序，从同一棵有根树中得到多棵不同的 chetree。例如，对于根为 1 且边为 (1, 2), (1, 3) 的有根树，通过改变顶点 1 的子节点顺序，可以得到两棵不同的 chetree：子节点顺序为 (2, 3) 或 (3, 2)。

如果两棵具有 $n$ 个顶点的 chetree 对于每个 $i = 1, 2, \dots, n$，其第 $i$ 个顶点的子节点集合相同且顺序也相同，则我们认为这两棵 chetree 相等。

给定一个整数 $n$ 和一个大小为 $n$ 的数组 $a$。 请计算有多少种不同的、标号为 $1, 2, \dots, n$ 的 $n$ 顶点 chetree，使得对于每个 $i$，顶点 $i$ 所在的层数不大于 $a_i$。我们将顶点的层数定义为它到根的距离。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100$)：顶点数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < n$)。

输出格式

输出一个整数：答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

1
0

样例输出 1

1

样例输入 2

2
1 1

样例输出 2

2

样例输入 3

3
0 1 2

样例输出 3

3