İnək gimnastları
Ferma həyatından bezən inəklər sirkə qoşulublar. Onlarla birlikdə yeni bir şou hazırlanır. Şou üçün səhnə dairəvi şəkildə yerləşdirilmiş n platformadan ibarətdir. Hər platformada 1-dən n-ə qədər inək bir-birinin üstünə çıxaraq bir yığın əmələ gətirir (bir inək digərinin üstünə çıxır). Manejin rəhbərinin siqnalı ilə bütün yığınlar saat əqrəbi istiqamətində "yıxılır", belə ki, yığının altındakı inək hərəkət etmir, onun üstündəki inək saat əqrəbi istiqamətində bir platforma irəliləyir, növbəti inək iki platforma və s. Nəticədə yeni inək yığınları yaranır.
Manejin rəhbəri düşünür ki, yığınlar yıxıldıqdan sonra hər platformadakı yeni yığınların sayı ilkin yığınların sayı ilə eyni olarsa, şou daha yaxşı olacaq. Biz yığınların konfiqurasiyasını "sehrli" adlandırırıq, əgər bu şərtə cavab verirsə. "Sehrli" konfiqurasiyaların sayını hesablayın. Bu rəqəm çox böyük ola biləcəyi üçün onu 10^9 + 7 moduluna görə çıxarın.
İki konfiqurasiya fərqli sayılır, əgər bu iki konfiqurasiyadan birində hər hansı bir platformada inəklərin sayı fərqlidirsə.
Giriş məlumatları
Bir tam ədəd n (1 ≤ n ≤ 10^12).
Çıxış məlumatları
Bir tam ədəd - 10^9 + 7 moduluna görə sehrli konfiqurasiyaların sayı.
Nümunə
n = 4 üçün uyğun konfiqurasiyalar: (1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4), (2, 3, 2, 3) və (3, 2, 3, 2).