Generic Cow Protests#2599

Generic Cow Protests

1 second

128 megabytes

Very easy

$n$ cows are lined up in a row and numbered from $1$ to $n$ . Each cow $i$ holds a sign with an integer $a_{i}$ a_i.

It is required to divide the cows into one or more contiguous groups so that each cow belongs to exactly one group, and the sum of the numbers in each group is nonnegative.

Count the number of ways to do this, modulo $1 0^{9} + 9$ 10^9 + 9.

For example, if $n = 4$ n = 4 and the numbers on the cows' signs are $2, 3, - 3, 1$ 2, 3, -3, 1, there are four possible ways to group the cows:

(2 3 -3 1)
(2 3 -3) (1)
(2) (3 -3 1)
(2) (3 -3) (1)

Input

The first line contains one integer $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5). Each of the following $n$ lines contains one integer $a_{i}$ a_i ( $- 1 0^{4} \leq a_{i} \leq 1 0^{4}$ -10^4 \leq a_i \leq 10^4).

Output

Print a single integer — the number of ways to group the cows, modulo $1 0^{9} + 9$ 10^9 + 9.

Examples

Example 1