Problem1046--数组分拆

1046: 数组分拆

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 289  Solved: 102
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI得到了一个数组作为他的新年礼物,他非常喜欢这个数组!

在仔细研究了几天之后,PIPI成功的将这个数组拆成了若干段,并且每段的和都不为0!

现在PIPI希望知道,这样的拆分方法一共有多少种?

两种拆分方法被视作不同,当且仅当数组断开的所有位置组成的集合不同。

Input

多组数据。

每组输入的第一行为一个正整数N,表示这个数组的长度

第二行为N个整数A1~AN,描述PIPI收到的这个数组

对于40%的数据,满足1<=N<=10

对于100%的数据,满足1<=N<=100000, |Ai|<=100

Output

对于每组输入,输出一行Ans,表示拆分方案的数量除以(10^9+7)的余数。

Sample Input

5
1 -1 0 2 -2

Sample Output

5

HINT

可以先用O(N^2)的方法骗分哦~

Source/Category