#P8096. [USACO22JAN] Drought G

[USACO22JAN] Drought G

题目描述

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

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

FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。尽管他不知道他的奶牛们具体的饥饿度,他知道每一头奶牛的饥饿度上界;具体地说,第 ii 头奶牛的饥饿度 hih_i 至多为 HiH_i0Hi10000\le H_i\le 1000)。

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

输入格式

输入的第一行包含 NN

第二行包含 H1,H2,,HNH_1,H_2,\ldots,H_N

输出格式

输出符合条件的饥饿度的 NN 元组数量,对 109+710^9+7 取模。

3
9 11 7
241
4
6 8 5 9
137

提示

【样例解释】

共有 (9+1)(11+1)(7+1)(9+1)\cdot (11+1)\cdot (7+1)33 元组 hhHH 相符合。

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

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

【数据范围】

  • 编号为偶数的测试点中的 NN 均为偶数,编号为奇数的测试点中的 NN 均为奇数。

  • 测试点 3-4 满足 N6N\le 6 以及 Hi10H_i \le 10

  • 测试点 5-10 满足 N50N\le 50 以及 Hi100H_i \le 100

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