题目描述

给定长度为 $n$ 的序列，可以给任意一个数加上正号或者负号，求有多少种连续子段和为 0 的情况。

输入格式

第一行包含 $n$ ($1\le n\le1000$)。第二行包含 $a_1,a_2...a_n$ ($1\le a_i\le 1000$)，序列的和小于等于 10000。

输出格式

输出连续子段和为 0 的方案数模 $10^9+7$。

4
1 1 1 1

12