eolymp
bolt
Try our new interface for solving problems
Məsələlər

Yenilikçi asılqan

Yenilikçi asılqan

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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. nk 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ə nk 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.

Giriş verilənləri #1
3 2
Çıxış verilənləri #1
5
Giriş verilənləri #2
5 10
Çıxış verilənləri #2
19
Mənbə EJOI 2019 Day1