eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Обычные протесты коров

Обычные протесты коров

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

n коров фермера Джона выстроены в ряд и пронумерованы от 1 до n. Коровы проводят еще один из своих странных протестов, поэтому каждая корова i держит табличку с целым числом a[i].

ФД знает, что стадо коров будет хорошо себя вести, если они правильно сгруппированы, и поэтому хотел бы распределить коров в одну или несколько смежных групп так, чтобы каждая корова входила ровно в одну группу и чтобы каждая группа имела неотрицательную сумму.

Помогите ему подсчитать количество способов, которыми он может это сделать, по модулю 10^9 + 9.

Например, если n = 4, а знаки коров равны 2, 3, -3 и 1, то существует только четыре способа размещения коров:

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

Вхідні дані

Первая строка содержит одно целое число n (1n10^5). Каждая строка от 2 до n + 1 содержит одно целое число a[i] (-10^4a[i]10^4).

Вихідні дані

Выведите одно целое число - количество расположений по модулю 10^9 + 9.

Приклад

Вхідні дані #1
4
2
3
-3
1
Вихідні дані #1
4
Джерело 2011 USACO Февраль Золото