Subsequence and Prefix Sum

时间限制：2s
空间限制：1024MB

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。你需要恰好进行一次如下操作：

选择一个非空子序列的下标 $1\le i_1<i_2<\cdots<i_k\le N$，并同时将每个 $A_{i_j}$ 替换为 $\sum_{x=1}^{j}A_{i_x}$。未被选择的位置保持不变。

求操作后可能得到的不同序列数量，对 $10^9+7$ 取模。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出不同结果序列的数量对 $10^9+7$ 取模后的值。

样例输入 1

3
1 1 2

样例输出 1

4

样例输入 2

4
1 -1 1 -1

样例输出 2

8

样例输入 3

5
0 0 0 0 0

样例输出 3

1

样例输入 4

40
2 -2 1 3 -3 -1 -2 -3 0 -1 -2 0 -3 0 0 2 0 -1 2 -2 -2 -1 3 -2 -2 -2 2 3 2 -3 0 -2 2 1 3 0 -1 0 -2 -3

样例输出 4

420429545

数据范围

对于所有数据，$1\le N\le 100$，$-10\le A_i\le 10$。