Yenilikçi asılqan
Yenilikçi asılqan
Yenilikçi asılqan n səviyyələrində bir-birinə bağlı çubuqlardan ibarətdir. Səviyyə i (i = [0, n-1] ilə) 2^i üfüqi çubuqlardan ibarətdir.
0-da olan çubuğun ortası divara yapışdırılıb. Bütün digər səviyyələrdə j-th (j= [1, 2^i] üçün) çubuğun ortası j/2-ci çubuğun sol tərəfinə yapışdırılır (bölərkən yuvarlaqlaşdırılır). Tək j üçün əvvəlki səviyyənin 2-a qədər və ya j cütdürsə, eyni çubuğun sağ tərəfinə. Son səviyyədəki hər çubuğun hər iki ucunda palto qarmaqları var. Qarmaqlar soldan sağa 1-dan 2^n-a qədər rəqəmlərlə nömrələnir. Məsələn, n = 3 üçün asılqan belə görünür:
Maşa bütün gödəkçələrini yeni asılqanına asmaq istəyir. Hər bir gödəkçənin çəkisi birə bərabərdir. Kövrək quruluşu pozmamaq üçün o, gödəkçələri elə qaydada asmalıdır ki, hər hansı bir çubuqun sol ucundakı ümumi çəki ilə başqa bir gödəkçə əlavə edildikdən sonra eyni çubuğun sağ ucundakı ümumi çəki arasındakı fərq ya 0 olsun. və ya 1. (Fizika qanunlarına görə, fərq -1-a bərabər ola bilər, lakin Maşa sağa əyilməni dəhşətli hesab edir.) Çubuqlar o qədər nazikdir ki, onların çəkisini nəzərə almamaq olar. Maşa sizin peşəkarlığınız haqqında çox eşitmişdir və sizdən kömək istəyir. n və k verilməklə, 10^9+7 qarmaq modulunun nömrəsini tapan proqram yazın ki, Maşa k-ci pillədə pencəyini asmalıdır.
Giriş verilənləri
Yeganə sətirdə n və k iki tam ədəd var.
Çıxış verilənləri
Bir tam ədədi çap edin — 10^9+7 modulunda k-ci addımda Maşanın pencəyini asmalı olduğu qarmaq nömrəsi.
Məhdudiyyətlər
n[1, 10^6]
k[1, min(2^n, 10^18)]
Nümunə
Birinci nümunədə qarmaqlar aşağıdakı ardıcıllıqla istifadə edilməlidir: 1, 5, 3, 7, 2, 6, 4, 8. İkinci mərhələdə Maşa pencəyini 5 nömrəli qarmaqdan asmalıdır.
İkinci misalda qarmaqların sırası belədir: 1, 17, 9, 25, 5, 21, 13, 29, 3, 19 və s.
3 2
5
5 10
19