eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Інноваційна вішалка

Інноваційна вішалка

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Інноваційна вішалка складається з n рівнів, що складаються із зв'язаних між собою стрижнів. Рівень i (при i = [0, n-1]) складається з 2^i горизонтальних стрижнів.

Середина стрижня на рівні 0 прикріплена до стіни. На інших рівнях середина j-го (при j= [1, 2^i]) стрижня прикріплена до лівої частини j/2-го стрижня (округлення вгору при розподілі на 2) попереднього рівня при непарному j, або до правої частини того ж стрижня при парному j. На обох кінцях кожного стрижня на останньому рівні висять гачки для одягу. Гачки пронумеровані зліва направо числами від 1 до 2^n. Наприклад, вішалка при n = 3 виглядає так:

Маша хоче повісити усі свої куртки на свою нову вішалку. Вага кожної куртки дорівнює одиниці. Щоб не зламати тендітну конструкцію, вона повинна вішати куртки в такому порядку, щоб різниця між загальною вагою на лівому кінці будь-якого стрижня і загальною вагою на правому кінці того ж стрижня після додавання чергової куртки дорівнювала 0 або 1. (За законами фізики різниця може бути рівна і -1, проте Маша вважає перекіс у правий бік жахливим.) Стрижні такі тонкі, що їх вагою можна знехтувати. Маша чула про ваш професіоналізм і просить вашої допомоги. Напишіть програму, яка за заданими n і k знаходить номер гачка по модулю 10^9+7, на який Маша повинна повісити куртку на k-му кроці.

Вхідні дані

На єдиному рядку задано два цілих числа n і k .

Вихідні дані

Виведіть одне ціле число - номер гачка, на який Маша повинна повісити куртку на k-му кроці по модулю 10^9+7.

Обмеження

  • n[1, 10^6]

  • k[1, min(2^n, 10^18)]

Приклад

Вхідні дані #1
3 2
Вихідні дані #1
5
Вхідні дані #2
5 10
Вихідні дані #2
19

Примітка

У першому прикладі гачки мають бути використані в наступному порядку: 1, 5, 3, 7, 2, 6, 4, 8. На другому кроці Маша має повісити свою куртку на гачок номер 5.

У другому прикладі порядок використання гачків такий: 1, 17, 9, 25, 5, 21, 13, 29, 3 , 19 і т.д.

Джерело EJOI 2019 Day1