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

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

Помогите ему подсчитать количество способов, которыми он может это сделать, по модулю 109 + 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 ≤ 105). Каждая строка от 2 до n + 1 содержит одно целое число ai (-104 ≤ ai ≤ 104).

Выходные данные

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