Adi inəklərin etirazları#2599
n inək sırayla düzülüb və 1-dən n-ə qədər nömrələnib. Hər bir inək i üzərində bir tam ədəd yazılmış lövhə tutur.
İnəkləri elə bir və ya bir neçə ardıcıl qrup şəklində bölmək tələb olunur ki, hər bir inək yalnız bir qrupa daxil olsun və hər bir qrupda olan ədədlərin cəmi qeyri-mənfi olsun.
Bunu neçə müxtəlif üsulla etmək olar? Cavabı 10^9 + 9 modulu üzrə verin.
Məsələn, əgər n = 4 və inəklərin üzərində yazılan ədədlər 2, 3, -3, 1 olarsa, inəkləri qruplaşdırmağın dörd müxtəlif yolu var:
(2 3 -3 1)
(2 3 -3) (1)
(2) (3 -3 1)
(2) (3 -3) (1)Birinci sətirdə bir tam ədəd (1 \leq n \leq 10^5) verilir. Sonrakı sətirdən hər birində bir tam ədəd (-10^4 \leq a[i] \leq 10^4) verilir.
Bir tam ədəd çıxışa yazın — inəkləri qruplaşdırmağın üsullarının sayını 10^9 + 9 modulu üzrə.
Nümunə 1