题目描述

Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，FJ 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。

FJ 的 $N$ 头奶牛（$1 \leq N \leq 100$）排成一行，队伍中的第 $i$ 头奶牛的饥饿度为一个非负整数 $h_i$。由于 FJ 的奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 $i$ 和 $i+1$ 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。

FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。尽管他不知道他的奶牛们具体的饥饿度，他知道每一头奶牛的饥饿度上界；具体地说，第 $i$ 头奶牛的饥饿度 $h_i$ 至多为 $H_i$（$0\le H_i\le 1000$）。

你的工作是计算符合上述上界的 $N$ 元组 $[h_1,h_2,\ldots,h_N]$ 的数量，使得 FJ 有可能达到他的目标，答案对 $10^9+7$ 取模。

输入格式

输入的第一行包含 $N$。

第二行包含 $H_1,H_2,\ldots,H_N$。

输出格式

输出符合条件的饥饿度的 $N$ 元组数量，对 $10^9+7$ 取模。

3
9 11 7

241

4
6 8 5 9

137

提示

【样例解释】

共有 $(9+1)\cdot (11+1)\cdot (7+1)$ 个 $3$ 元组 $h$ 与 $H$ 相符合。

$h=[8,10,5]$ 是其中一个元组。在这个情况中，有可能使得所有的奶牛具有相同的饥饿度：给奶牛 $2$ 和 $3$ 各两袋玉米，然后给奶牛 $1$ 和 $2$ 各五袋玉米，可以使得所有奶牛的饥饿度均为 $3$。

$h=[0,1,0]$ 是另一个元组。在这个情况中，不可能使得奶牛们的饥饿度相等。

【数据范围】

• 编号为偶数的测试点中的 $N$ 均为偶数，编号为奇数的测试点中的 $N$ 均为奇数。

• 测试点 3-4 满足 $N\le 6$ 以及 $H_i \le 10$。

• 测试点 5-10 满足 $N\le 50$ 以及 $H_i \le 100$。

• 测试点 11-20 没有额外限制。