Problem Statement

Captain Ascending has discovered an ancient treasure map that reveals hidden fortunes along a mystical coastline.

The map is represented by an array A of length N, where each element A[i] indicates the treasure value (which may be negative or positive) at that location.

To unlock the ultimate riches, the captain believes his journey must be divided into segments in which the sum of treasures in each segment (called its "beauty") strictly increases as he moves from one segment to the next. The beauty of a range [L, R] in the array A is defined as the sum of the elements from A[L] to A[R].

The captain wishes to partition the array A into non-intersecting, contiguous subarrays such that, when each subarray is replaced by its beauty, the resulting sequence forms a strictly increasing progression.

Find the total number of ways to partition the array A into contiguous subarrays so that the sequence of beauties is strictly increasing. Since the answer can be very large, return it modulo 10^9 + 7.

Input Format

• The first line contains an integer, N, denoting the number of elements in A.
• Each of the N subsequent lines (where 0 <= i < N) contains an integer describing A[i].

Constraints

• 1 <= N <= 1000
• -10^9 <= A[i] <= 10^9

Sample Test Cases

Case 1

• Input:
  • 2
  • 1
  • 2
• Output:
  • 2
• Explanation:
  • For the array [1][2], there are two valid partitions:
    1. Single segment partition:
       • Partition: [1][2]
       • Beauty: 3
       • With only one segment, the condition is automatically satisfied.
    2. Two segment partition:
       • Partition: [1] and [2]
       • Beauties: 1 and 2, which is strictly increasing (since 1 < 2).
  • Thus, the total number of valid partitions is 2.