Iahub 意外发现了一个秘密实验室。他发现有n个设备排成一排,从左到右编号为1到n。每个设备 i (1 ≤ i ≤ n) 可以创建 ai 单位的物质或 ai 单位的反物质。
Iahub 希望在实验室中选择一些连续的设备子阵列,指定每个设备的生产模式(产生物质或反物质),最后为其拍照。然而,只有当所选子阵列中产生的物质和反物质数量相同时,他才会成功(否则照片中会出现溢出的物质或反物质)。
您需要计算 Iahub 可以成功拍照的不同方式的数量。如果一张照片代表另一个子阵列,或者如果该子阵列的至少一个设备被设置为在其中一张照片中产生物质并在另一张照片中产生反物质,则该照片与另一张照片不同。
输入
第一行包含一个整数 n (1 ≤ n ≤ 1000)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1000)。
a1 + a2 + ... + an 之和将小于或等于 10000。
输出
输出一个整数,Iahub 可以拍照的方式数,模 1000000007 (109 + 7)。
示例
输入 #1
4 1 1 1 1
输出 #1
12
注意
可能的照片为 [1+, 2-], [1-, 2+], [2+, 3-], [2-, 3+], [3+, 4-], [3-, 4+], [1+, 2+, 3-, 4-], [1+, 2-, 3+, 4-], [1+, 2-, 3-, 4+]、[1-、2+、3+、4-]、[1-、2+、3-、4+]和[1-、2-、3+、4+],其中“i+”表示第i个元素产生物质,“i-”表示第i个元素产生反物质。