Hamiltonian Hypercube

Hypercube graphs are very regular, and you have spent a lot of time on the mathematics around them. The vertices of a hypercube graph of dimension $n$ are all binary strings of length $n$, and two vertices are connected when they differ in exactly one position. Hypercube graphs are related to error-correcting codes in several ways.

One of those relationships involves the $n$-bit Gray Code, an ordering of the binary strings of length $n$ defined recursively. The words of the $n$-bit code start with the words of the $(n-1)$-bit code, each with a 0 prepended, followed by the same words in reverse order, each with a 1 prepended. The 1-bit Gray Code consists of 0 and 1. For example, the 3-bit Gray Code is this sequence:

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

The $n$-bit Gray Code forms a Hamiltonian path in the $n$-dimensional hypercube, a path that visits every vertex exactly once (see Figure 1).

Figure 1: the 3-dimensional hypercube and the Hamiltonian path that corresponds to the 3-bit Gray Code.

You wonder how many vertices lie between the vertices $0^n$ ($n$ zeros) and $1^n$ ($n$ ones) on that path. The count is at least $2^{n-1}-1$ and at most $2^n-2$, because $0^n$ is always the first vertex and $1^n$ sits somewhere in the second half of the path. Once you have answered that question, you want to generalise it and write a program that determines the number of vertices between two arbitrary vertices of the hypercube on the path given by the Gray Code.

The input is a single line containing:

• one integer $n$ ($1 \le n \le 60$), the dimension of the hypercube
• two binary strings $a$ and $b$, both of length $n$, where $a$ comes before $b$ in the $n$-bit Gray Code

Print the number of code words between $a$ and $b$ in the $n$-bit Gray Code.