Звичайні протести корів
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). Кожен з наступних n рядків містить одне ціле число a[i] (-10^4 ≤ a[i] ≤ 10^4).
Вихідні дані
Виведіть одне ціле число — кількість можливих розміщень за модулем 10^9 + 9.