Smallest LNR Sequence

An $n$-bit shift register is a memory that holds $n$ bits, and its contents can be changed in only two ways. The contents are shifted left by one position, and the rightmost bit is given a 0 or a 1. One such change is called a move. For example, when the contents of a 4-bit shift register are 0001, one move makes the contents either 0010 (a 0 is shifted in) or 0011 (a 1 is shifted in).

Start from an $n$-bit shift register whose contents are all zeroes. Build a sequence of moves so that after every move the contents differ from all past contents. An $n$-bit shift register has $2^n$ possible contents, so the longest such sequence has length $2^n$. For every $n$, at least one sequence of length $2^n$ exists. For $n = 3$ there are two sequences of length $2^3 = 8$.

$A$ = 000 001 010 101 011 111 110 100

$B$ = 000 001 011 111 110 101 010 100

LNR (Longest Non-Repeating) sequences

Given a positive integer $n$, consider any sequence with the following five properties.

1. Each element of the sequence is a bit-string of length $n$.
2. The sequence has $2^n$ elements.
3. No element repeats.
4. All $n$ bits of the first element are zero.
5. Every element other than the first comes from the element before it by one move as described above.

Such a sequence is a Longest-Non-Repeating sequence, or LNR sequence. For a positive integer $n$, the set of all LNR sequences is written $S(n)$.

The smallest LNR sequence

An LNR sequence $s \in S(n)$ gets a value $value(s)$ as follows. Concatenate the $2^n$ bit-strings of $s$ into a single bit-string, then read that bit-string as a binary number. For the LNR sequence $A$ above,

$value(A)$ = 000001010101011111110100

The smallest LNR sequence $s_{small}(n)$ is the sequence in $S(n)$ with the smallest $value(s)$. For $n = 3$ the only LNR sequences are $A$ and $B$, and $value(A) < value(B)$, so $s_{small}(3) = A$. The positions of the bit-strings 000, 001, 010, 101, 011, 111, 110, 100 in $A$ are 1, 2, 3, 4, 5, 6, 7, 8 respectively.

What you need to do

Given a positive integer $n \le 10$ and a bit-string $s$ of length $n$, compute $s_{small}(n)$ and print the position of $s$ in it. Print 1 if $s$ is the first element of $s_{small}(n)$, print 2 if it is the second element, and so on.

The input has two lines. The first line contains a positive integer $n \le 10$. The second line contains a bit-string $s$ of length $n$.

Print a single positive integer, the position of $s$ in $s_{small}(n)$.

Do not construct all LNR sequences and then pick the smallest one. You can find the smallest LNR sequence by trying the move that shifts in a 0 before the move that shifts in a 1.