Обычные протесты коров
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 (1 ≤ n ≤ 10^5). Каждая строка от 2 до n + 1 содержит одно целое число a[i] (-10^4 ≤ a[i] ≤ 10^4).
Выходные данные
Выведите одно целое число - количество расположений по модулю 10^9 + 9.