CF383D.Antimatter

Iahub accidentally discovered a secret lab. He found there n devices ordered in a line, numbered from 1 to n from left to right. Each device i (1 ≤ i ≤ n) can create either a__i units of matter or a__i units of antimatter.

Iahub wants to choose some contiguous subarray of devices in the lab, specify the production mode for each of them (produce matter or antimatter) and finally take a photo of it. However he will be successful only if the amounts of matter and antimatter produced in the selected subarray will be the same (otherwise there would be overflowing matter or antimatter in the photo).

You are requested to compute the number of different ways Iahub can successful take a photo. A photo is different than another if it represents another subarray, or if at least one device of the subarray is set to produce matter in one of the photos and antimatter in the other one.

Iahub 不小心发现了一个秘密实验室。他在其中找到了按从左到右顺序排列的 $ n $ 个设备，编号为 $ 1 $ 到 $ n $。每个设备 $ i $（$ 1 \leq i \leq n $）可以生成 $ a_i $ 单位的物质，或 $ a_i $ 单位的反物质。

Iahub 想要从实验室中选出某个连续子数组的设备，为其中每个设备指定其生产模式（生成物质或反物质），并最终为其拍照。然而，只有当所选子数组中生成的物质总量与反物质总量相等时，他才能成功（否则照片中会出现物质或反物质溢出）。

你需要计算 Iahub 成功拍照的不同方式总数。若两张照片所对应的子数组不同，或在两张照片中至少有一个设备被设定为在一张中生成物质、而在另一张中生成反物质，则认为这两张照片是不同的。

The first line contains an integer n (1 ≤ n ≤ 1000). The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 1000).

The sum _a_1 + _a_2 + ... + a__n will be less than or equal to 10000.

第一行包含一个整数 $n$（$1 \leq n \leq 1000$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 1000$）。

和 $a_1 + a_2 + \dots + a_n$ 不超过 $10000$。

Output a single integer, the number of ways Iahub can take a photo, modulo 1000000007 (109 + 7).

输出一个整数，表示 Iahub 拍照的方式数目，对 $1000000007$（即 $10^9 + 7$）取模。

The possible photos are [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+] and [1-, 2-, 3+, 4+], where "i+" means that the i-th element produces matter, and "i-" means that the i-th element produces antimatter.

可能的照片有 [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 个元素产生反物质。