해밀턴 하이퍼큐브

하이퍼큐브 그래프는 규칙성이 뚜렷해서, 당신은 이 그래프와 얽힌 수학을 오랫동안 공부했다. 차원이 $n$인 하이퍼큐브 그래프의 정점은 길이가 $n$인 이진 문자열 전체이고, 두 정점은 정확히 한 자리만 다를 때 간선으로 이어진다. 하이퍼큐브 그래프는 오류 정정 부호와 여러 방식으로 이어져 있다.

그중 하나가 $n$비트 그레이 코드이다. $n$비트 그레이 코드는 길이가 $n$인 이진 문자열을 늘어놓은 순서이며, 다음과 같이 재귀적으로 정의한다. $n$비트 코드의 앞부분은 $(n-1)$비트 코드의 각 단어 앞에 0을 붙인 것이고, 뒷부분은 같은 단어를 역순으로 놓고 각 단어 앞에 1을 붙인 것이다. 1비트 그레이 코드는 0과 1로 이루어진다. 예를 들어 3비트 그레이 코드는 다음 순서이다.

000, 001, 011, 010, 110, 111, 101, 100

$n$비트 그레이 코드는 $n$차원 하이퍼큐브의 해밀턴 경로, 곧 모든 정점을 정확히 한 번씩 지나는 경로를 이룬다 (그림 1).

그림 1: 3차원 하이퍼큐브와 3비트 그레이 코드에 대응하는 해밀턴 경로.

당신은 이 경로에서 정점 $0^n$ (0이 $n$개)과 $1^n$ (1이 $n$개) 사이에 정점이 몇 개 있는지 궁금하다. $0^n$은 언제나 첫 번째 정점이고 $1^n$은 경로의 뒤쪽 절반 어딘가에 있으므로, 그 개수는 $2^{n-1}-1$ 이상 $2^n-2$ 이하이다. 이 질문의 답을 찾은 뒤에는 문제를 일반화해서, 그레이 코드가 정하는 경로 위에서 하이퍼큐브의 임의의 두 정점 사이에 있는 정점의 개수를 구하는 프로그램을 작성하려고 한다.

첫째 줄에 다음이 순서대로 주어진다.

• 하이퍼큐브의 차원을 나타내는 정수 $n$ ($1 \le n \le 60$)
• 길이가 $n$인 이진 문자열 $a$와 $b$. $n$비트 그레이 코드에서 $a$는 $b$보다 앞에 있다.

$n$비트 그레이 코드에서 $a$와 $b$ 사이에 있는 코드 단어의 개수를 출력한다.