Qızıl açar və ya Buratinin macəraları
Son zamanlar Buratino, "seqment ağacı" adlı bir məlumat strukturu ilə maraqlanmağa başladı.
Seqment ağacı, hər bir zirvəsi [l; r] sərhədləri ilə bir seqment haqqında müəyyən məlumat saxlayan ikili ağacdır. Ağacın kökü, N ardıcıllığının uzunluğu olduğu halda, bütün ardıcıllıq haqqında məlumat saxlayan zirvədir. Digər zirvələr üçün belədir: əgər l r-ə bərabərdirsə, bu zirvə yarpaqdır. Əks halda, [l; m] və [m+1, r] seqmentləri haqqında məlumat saxlayan iki övladı var. Seqment ağacı ən effektiv şəkildə, [l; m] və [m+1, r] seqmentlərinin uzunluqları bərabər olduqda qurulur. Lakin, verilmiş [l; r] seqmentinin uzunluğu tək olduqda, onu iki bərabər seqmentə bölmək mümkün deyil. Bu halda sol və ya sağ seqment digərindən bir vahid uzun olacaq. Hər çıxışdan sonra Buratino N uzunluğunda bir massiv üçün bəzi seqment ağacını çəkir. Hər dəfə seqmentləri bərabər etmək mümkün olmadıqda, təsadüfi olaraq sol və ya sağ seqmenti daha uzun etməyi seçir.
Sizin vəzifəniz, Buratino'nun çəkə biləcəyi fərqli ağacların sayını hesablamaqdır.
Giriş verilənləri
Tək bir sətirdə Buratino'nun seqment ağacı quracağı massiv ölçüsü olan N (1 ≤ N ≤ 2·10^9) verilmişdir.
Çıxış verilənləri
Tək bir sətirdə Buratino'nun çəkə biləcəyi fərqli ağacların sayını çıxarın. Cavab çox böyük ola biləcəyi üçün onu 10^9+7 modulu ilə çıxarın.