P6970: 饥饿度
传统题
1.000s
时间限制
256MB
内存限制
3 提交
2 解决
【题目描述】
【题目描述】
Farmer John
的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，FJ 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。
FJ
的 N 头奶牛（1≤N≤100）排成一行，队伍中的第 i
头奶牛的饥饿度为一个非负整数 hi。由于 FJ
的奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 i 和 i+1 并分别喂她们一袋玉米，令她们的饥饿度各减少 1。
FJ
想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。尽管他不知道他的奶牛们具体的饥饿度，他知道每一头奶牛的饥饿度上界；具体地说，第 i 头奶牛的饥饿度 hi 至多为 Hi（0≤Hi≤1000
）。
你的工作是计算符合上述上界的 N
元组 [h1,h2,…,hN] 的数量，使得 FJ 有可能达到他的目标，答案对 10
^9+7
取模。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。
第二行包含 H1,H2,…,HN
。
【
输出格式】
（输出至终端 /
标准输出）：
输出符合条件的饥饿度的 N
元组数量，对 10
^9+7
取模。
【
输入样例】
：
3
9 11 7
【
输出样例】
：
241
【样例说明】
共有 (9+1)×(11+1)×(7+1)
个 3 元组 h 与 H 相符合。
h=[8,10,5]
是其中一个元组。在这个情况中，有可能使得所有的奶牛具有相同的饥饿度：给奶牛 2 和 3 各两袋玉米，然后给奶牛 1 和 2 各五袋玉米，可以使得所有奶牛的饥饿度均为 3。
h=[0,1,0]
是另一个元组。在这个情况中，不可能使得奶牛们的饥饿度相等。
【
输入样例】
：
4
6 8 5 9
【
输出样例】
：
137
【
测试点性质】
：
编号为偶数的测试点中的 N
均为偶数，编号为奇数的测试点中的 N 均为奇数。
测试点 3-4
满足 N≤6 以及 Hi≤10。
测试点 5-10
满足 N≤50 以及 Hi≤100。
测试点 11-20
没有额外限制。