Contiguous Cow Partitioning

Farmer John has (N) cows arranged in a line, where the (i)-th cow has a rationality value (a_i). He wishes to split the cows into contiguous groups such that the sum of the rationality values in each group is non-negative.

Let the prefix sum be defined as (P_i = \sum_{j=1}^{i} a_j) with (P_0 = 0). A valid group spanning from cow (j+1) to cow (i) must satisfy (P_i - P_j \ge 0) or equivalently (P_j \le P_i).

Define (dp[i]) as the number of ways to partition the first (i) cows into valid groups. Then, (dp[0] = 1) and for (i \ge 1) [ dp[i] = \sum_{\substack{0 \le j < i \ P_j \le P_i}} dp[j]. ] Because (N) can be as large as (10^5) and individual values may be negative, an efficient solution uses a Binary Indexed Tree (Fenwick Tree) after coordinate compressing the prefix sums.

The answer should be computed modulo (10^9+7).

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 10^5\)), the number of cows.

The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\) (\(-10^4 \leq a_i \leq 10^4\)), representing the rationality values of the cows.

outputFormat

Output a single integer, the number of ways to partition the cows into contiguous groups where each group's sum is non-negative modulo \(10^9+7\).

sample

3
2 -5 3

2