AT_arc180_c [ARC180C] Subsequence and Prefix Sum

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。

你需要恰好进行 $1$ 次如下操作：

• 选择 $A$ 的一个（不一定连续的）非空子序列，并将其替换为其累积和。更准确地说，首先选择满足 $1 \leq i_1 < i_2 < \cdots < i_k \leq N$ 的下标序列 $(i_1,i_2,\cdots,i_k)$，其中 $k$ 的取值范围为 $1 \leq k \leq N$，你可以自由选择 $k$。然后，对于每个 $j$（$1 \leq j \leq k$），将 $A_{i_j}$ 的值替换为 $\sum_{1 \leq x \leq j} A_{i_x}$。所有替换操作同时进行。

请你求出，操作后可能得到的不同 $A$ 序列的个数，结果对 $10^9+7$ 取模。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出答案。

样例 1

输入

3
1 1 2

输出

4

样例 2

输入

4
1 -1 1 -1

输出

8

样例 3

输入

5
0 0 0 0 0

输出

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

输出

420429545

说明/提示

限制条件

• $1 \leq N \leq 100$
• $-10 \leq A_i \leq 10$
• 输入的所有数都是整数

样例解释 1

操作后可能得到的 $A$ 有如下 $4$ 种：

• $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)$ 即可实现。

由 ChatGPT 4.1 翻译