격자 방문 순서

문제

크기가 $2^N \times 2^N$인 격자가 있다. 이 격자를 Z 모양으로 방문한다.

$2 \times 2$ 격자의 경우 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 방문한다. $N > 1$인 경우, 격자를 4등분하여 재귀적으로 같은 순서로 방문한다. 즉, $2^N \times 2^N$ 격자를 $2^{N-1} \times 2^{N-1}$ 크기의 4개 사분면으로 나누고, 각 사분면을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 재귀적으로 탐색한다.

정수 $N$, $r$, $c$가 주어졌을 때 $r$행 $c$열 칸을 몇 번째로 방문하는지 구하라. 방문 순서는 0부터 시작한다.

입력

첫째 줄에 세 정수 $N$, $r$, $c$가 공백으로 구분되어 주어진다.

제한

• $1 \le N \le 15$
• $0 \le r, c < 2^N$

출력

$(r, c)$ 칸의 방문 순서를 출력하라.

입출력 예시

입력 1

2 3 1

출력 1

11

입력 2

3 7 7

출력 2

63

입력 3

1 0 0

출력 3

0

입력 4

10 511 511

출력 4

262143

입력 5

4 7 7

출력 5

63