分数: 600 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N.
您将执行以下操作一次:
- 选择一个非空子序列 A (不一定是连续的)并将其替换为其累积和。 更准确地说,首先选择一系列索引 (i_1,i_2,\cdots,i_k) 这样 1 \leq i_1 < i_2 < \cdots < i_k \leq N。 序列的长度 k (1 \leq k \leq N) 可以自由选择。 然后,对于每个 j (1 \leq j \leq k),替换值 A_{i_j} 与 \sum_{1 \leq x \leq j} A_{i_x}。 对所有选定的索引同时进行此替换。
查找,取模 10^9+7,可能的序列数 A 操作后。
约束
- 1 \leq N \leq 100
- -10 \leq A_i \leq 10
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
3 1 1 2
示例输出 1
4
可能的序列 A 运行后如下:
- A=(1,1,2):这可以通过以下方式实现 k=1 和 (i_1)=(1).
- A=(1,2,2):这可以通过以下方式实现 k=2 和 (i_1,i_2)=(1,2).
- A=(1,1,3):这可以通过以下方式实现 k=2 和 (i_1,i_2)=(1,3).
- A=(1,2,4):这可以通过以下方式实现 k=3 和 (i_1,i_2,i_3)=(1,2,3).
示例输入 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