미녀와 야수는 요즘 유행하는 인기 TV 쇼의 제목이다.

이 TV 쇼에서 게스트로 초대된 미녀 영화배우는, 깊이가 N인 이진 트리 미로에 갇힌다.

게스트는 이진 트리의 루트 노드(정점)에서 시작하여, 출구가 있는 리프(자식이 없는 노드)까지 걸어가며,이 모습이 생중계되는 방식이다.

각 리프 노드에는 출구가 있으며, 출구 밖에는 야수가 있을 수도 있고, 동현, 딧불, 건우 등의 유명 남배우들이 대기하고 있을 수도 있다.

이진 트리의 각 노드는 고유한 번호가 있으며, 루트 노드가 1번이고, 각 노드 X의 왼쪽 자식은 2X, 오른쪽 자식은 2X + 1의 번호를 가지고 있다.

사실 우리의 미녀 게스트는, 방송 특성상 몇 번째 방에서 어느 방향으로 가야 하는지를 이미 지령 받은 상태로 시작한다.

첫 번째 방에서는 왼쪽, 두 번째 방에서는 오른쪽… 이런 식으로 말이다.

문제는 불쌍한 게스트가 “왼쪽”이 어느 방향이고 “오른쪽”이 어느 방향인지 헷갈려 한다는 것이다.

여러분이 게스트라고 상상해 보자.

트리 구조대로라면 트리의 왼쪽 자식이 왼쪽 방향이겠지만, (그림1)

게스트가 노드 위에 서서 자식 노드 방향으로 앞을 바라보면, 오른쪽 자식이 왼쪽으로 보일 것이다. (그림 2)

그림1

그림 2

그래서 게스트는 진행 도중에 K번, 그림 1처럼 트리 구조대로 좌우를 판단할지, 아니면 그림 2처럼 자기 시선에서 좌우를 판단할지에 관하여 마음을 바꾼다.

마음의 변화는 각 노드에서 최대 한 번씩만 일어난다.

시작하자마자 루트 노드에서 마음을 바꿀 수도 있다.

TV쇼 시작 전에는, 게스트의 마음(방향감각)이 그림 1과 같은 트리 구조 기준일 수도 있고, 그림 2와 같은 자기 시선 기준일수도 있다.

미남 배우들은 리프 노드 중, 그 번호가 A이상 B이하인 노드에 있다.

미녀 게스트가 정확히 K번 마음을 바꿔서 갈 수 있는 리프 노드 중, A이상 B이하인 노드의 번호의 합을 출력하는 프로그램을 작성하라.

답이 클 수 있으므로, 10억 7로 나눈 나머지를 출력한다.

미녀와 야수 timer 1s memory 512MB

미녀와 야수 1s 512MB