样例下载

题目描述

有 $N$ 个非负整数排成一排，第 $i$ 个整数为 $X_i$。

你可以进行以下操作：任意选择相邻的两个整数并分别减一。

你可以操作任意次。

现在，经过你的操作，你已经得到了若干个相同的非负整数。你准备对你的操作过程进行复盘，却忘了开始的 $N$ 个数是什么了。好在你知道，初始数列的每个数都是有上限的，第 $i$ 个整数 $X_i$ 的上限为 $T_i$，即 $X_i ≤ T_i$。

问：开始时给出的数列有多少种可能？答案可能很大，你需要输出答案 $mod$ $(10^9+7)$。

输入格式

第一行：一个整数 $N$

第二行：$N$ 个整数 $T_i$

输出格式

一个整数，表示答案 $mod$ $(10^9+7)$

输入样例

3
1 2 1

输出样例

5

样例解释

5 种可能的初始数列为：

0 0 0
0 1 1
1 1 0
1 1 1
1 2 1

数据范围

• 20% 的数据：$N ≤ 10$, $0 ≤ T_i ≤ 10$;

• 50% 的数据：$N ≤ 50$, $0 ≤ T_i ≤ 100$;

• 100% 的数据：$1 ≤ N ≤ 100$, $0 ≤ T_i ≤ 1000$.

另外：

• 50% 的数据：所有组数据的 $N$ 均为偶数;

• 50% 的数据：所有组数据的 $N$ 均为奇数;