행거
시간 제한1초메모리 제한512 MB
2^n개의 고리가 달린 이진 구조의 걸이대에서, 각 막대의 좌우 무게 차가 0 또는 1이 되도록 코트를 걸 때 k번째 단계에 사용하는 고리의 번호를 1e9+7로 나눈 나머지로 구한다.
문제
행거는 n개의 층으로 이루어진 막대 구조이다. 층 i (단, i ∈ {0, 1, ..., n-1})는 2i개의 막대로 이루어져 있다. 0층 막대의 중점은 벽에 고정되어 있다. 나머지 층에서 j번째 막대(단, j ∈ {1, ..., 2i})의 중점은 이전 층 ⌈j/2⌉번째 막대의 왼쪽 끝(j가 홀수일 때) 또는 오른쪽 끝(j가 짝수일 때)에 고정되어 있다. 마지막 층에서 각 막대의 양쪽 끝에는 코트를 걸 수 있는 고리가 있다. 고리는 왼쪽에서 오른쪽 순서대로 1부터 2n까지 번호가 매겨져 있다.
예를 들어 n = 3인 행거는 다음과 같다.
Mojca는 자신의 코트를 모두 행거에 걸고 싶어한다. 모든 코트의 무게는 정확히 1단위이다. 연약한 구조가 부서지지 않도록 Mojca는 코트를 어떤 순서로 걸어야 하며, 임의의 막대에 대해 왼쪽 끝에 걸린 총 무게 wl과 오른쪽 끝에 걸린 총 무게 wr의 차이는 0 또는 1이어야 한다(wl - wr ∈ {0, 1}). (물리 법칙에 따르면 차이가 -1일 수도 있지만, 오른쪽으로 기우는 행거는 Mojca에게 정말 보기 싫다.) 막대는 너무 얇아서 무게를 무시할 수 있다.
Mojca는 여러분의 문제 해결 실력을 듣고 도움을 청한다. 정수 n과 정수 k를 읽고, Mojca가 k번째 코트를 걸어야 하는 고리의 번호를 (109 + 7)로 나눈 나머지를 출력하는 프로그램을 작성하라.
입력
입력은 한 줄로 이루어져 있으며, 공백으로 구분된 정수 n과 k가 주어진다.
출력
k번째 단계에서 사용할 고리의 번호를 (109 + 7)로 나눈 나머지를 출력한다.
제한
- n ∈ [1, 106]
- k ∈ [1, min{2n, 1018}]