C - Subsequence and Prefix Sum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

長さ 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) も自由に選べる． その後，各 j (1 \leq j \leq k) について，A_{i_j} の値を \sum_{1 \leq x \leq j} A_{i_x} で置き換える． この置き換えはすべて同時に行う．

操作後の A としてあり得る数列の個数を 10^9+7 で割ったあまりを求めてください．

制約

  • 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 としてありうるのは以下の 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) とすれば達成できます．

入力例 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

Score : 600 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N.

You will perform the following operation exactly once:

  • Choose a non-empty subsequence of A (not necessarily contiguous) and replace it with its cumulative sums. More precisely, first choose a sequence of indices (i_1,i_2,\cdots,i_k) such that 1 \leq i_1 < i_2 < \cdots < i_k \leq N. The length of the sequence k (1 \leq k \leq N) can be chosen freely. Then, for each j (1 \leq j \leq k), replace the value of A_{i_j} with \sum_{1 \leq x \leq j} A_{i_x}. This replacement is done simultaneously for all chosen indices.

Find, modulo 10^9+7, the number of possible sequences A after the operation.

Constraints

  • 1 \leq N \leq 100
  • -10 \leq A_i \leq 10
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

3
1 1 2

Sample Output 1

4

The possible sequences A after the operation are as follows:

  • A=(1,1,2): This can be achieved with k=1 and (i_1)=(1).
  • A=(1,2,2): This can be achieved with k=2 and (i_1,i_2)=(1,2).
  • A=(1,1,3): This can be achieved with k=2 and (i_1,i_2)=(1,3).
  • A=(1,2,4): This can be achieved with k=3 and (i_1,i_2,i_3)=(1,2,3).

Sample Input 2

4
1 -1 1 -1

Sample Output 2

8

Sample Input 3

5
0 0 0 0 0

Sample Output 3

1

Sample Input 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

Sample Output 4

420429545