← 返回题目列表

AtCoder · arc180_c

C. 子序列和前缀和

中文机器翻译题面 查看原题

分数: 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