Звичайні протести корів#2599

Звичайні протести корів

1 секунда

128 мегабайтів

Дуже легка

$n$ корів стоять у ряд і пронумеровані від $1$ до $n$ . Кожна корова $i$ тримає табличку з цілим числом $a_{i}$ a_i.

Потрібно розділити корів на одну або більше суміжних груп так, щоб кожна корова належала рівно одній групі, а сума чисел у кожній групі була невід'ємною.

Порахуйте кількість способів зробити це, взявши результат по модулю $1 0^{9} + 9$ 10^9 + 9.

Наприклад, якщо $n = 4$ n = 4, а числа на табличках корів такі: $2, 3, - 3, 1$ 2, 3, -3, 1, можливі чотири способи згрупувати корів:

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

Вхідні дані

У першому рядку дано одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5). Кожен із наступних $n$ рядків містить одне ціле число $a_{i}$ a_i ( $- 1 0^{4} \leq a_{i} \leq 1 0^{4}$ -10^4 \leq a_i \leq 10^4).

Вихідні дані

Виведіть одне ціле число — кількість способів згрупувати корів, по модулю $1 0^{9} + 9$ 10^9 + 9.

Приклади

Приклад 1