Adi inəklərin etirazları
n fermerin inəkləri sıraya düzülüb və 1-dən n-ə qədər nömrələnib. Hər bir inək i tam ədəd a[i] olan lövhə tutur.
FJ bilir ki, inəklər düzgün qruplaşdırıldıqda yaxşı davranacaqlar. Buna görə də, inəkləri bir və ya bir neçə ardıcıl qrupa bölmək istəyir ki, hər bir inək yalnız bir qrupa daxil olsun və hər bir qrupun cəmi qeyri-mənfi olsun.
Bu qruplaşdırmanı neçə fərqli üsulla edə biləcəyinizi 10^9 + 9 moduluna görə hesablayın.
Məsələn, əgər n = 4 və inəklərin lövhələrindəki rəqəmlər 2, 3, -3 və 1-dirsə, inəkləri qruplaşdırmağın dörd yolu var:
(2 3 -3 1) (2 3 -3) (1) (2) (3 -3 1) (2) (3 -3) (1)
Giriş məlumatları
Birinci sətir bir tam ədəd n (1 ≤ n ≤ 10^5) ehtiva edir. 2-dən n + 1-ə qədər olan hər bir sətir bir tam ədəd a[i] (-10^4 ≤ a[i] ≤ 10^4) ehtiva edir.
Çıxış məlumatları
Bir tam ədəd çıxarın - qruplaşdırma üsullarının sayını 10^9 + 9 moduluna görə.