21320번 - 순간이동 여행

문제

민겸이는 높이가 N인 포화 이진 트리를 여행하기로 했다. 높이가 N인 포화 이진 트리란, 루트 노드에서 어떤 리프 노드까지 이동할 때 최소 N - 1번 이동해야 하는 포화 이진 트리를 말한다. 각 노드에는 번호가 매겨져 있는데, 루트 노드는 1번이고, 모든 인터널 노드(리프 노드가 아닌 노드)에 대해 인터널 노드가 P번 노드일 때, 해당 노드의 왼쪽 자식은 P × 2번 노드이고, 오른쪽 자식은 P × 2 + 1번 노드이다.

아래 그림은 높이가 4인 포화 이진 트리의 예시이다.

민겸이는 여행을 위해 어떤 노드에 도착했다. 민겸이는 자신이 위치한 노드와 연결된 인접한 노드로 걸어서 이동할 수 있다. 하지만 민겸이는 한 번 방문했던 노드를 다시는 방문하지 않는다. 이 때문에 모든 노드를 방문할 수 없을 수도 있다는 것을 깨달은 민겸이는 순간이동기를 준비했다. 순간이동기는 민겸이를 방문하지 않은 노드 중 원하는 노드로 순간이동시켜준다. 하지만, 순간이동 할 때마다 엄청난 돈이 들기 때문에, 민겸이는 순간이동 횟수를 최소화하고 싶다.

민겸이가 여행을 시작할 노드 번호가 주어질 때, 민겸이가 모든 노드를 방문하기 위해서 순간이동을 최소 몇 번 해야 하는지 알아보자.

입력

포화 이진 트리의 높이 N(1 ≤ N ≤ 3,000), 정수 K(1 ≤ K ≤ N)가 주어진다. 민겸이는 2^{K - 1}번 노드에서 여행을 시작한다.

출력

민겸이가 모든 노드를 방문할 때까지 순간이동을 최소 몇 번 해야 하는지 출력한다. 단, 답이 너무 커질 수 있으므로, 답을 10⁹ + 7로 나눈 나머지를 출력한다.

제한

힌트