Neçə artan - 2#5976
Verilmiş ardıcıllıq N tam ədəddən ibarət olsun.
Bu ardıcıllığın ciddi artan altardıcıllıqlarının sayını tapın.
Giriş faylının birinci sətirində N ədədi verilir. İkinci sətirdə isə bir və ya bir neçə boşluqla ayrılmış N tam ədəd verilir, yəni ardıcıllığın elementləri (1 ≤ N ≤ 100000, elementlərin modulu 1,25·10^5-dən böyük deyil).
Yeganə sətirdə məsələnin cavabını verin. Cavabı 1000000009 (10^9+9) modulu ilə hesablayın.
Nümunə 1