가장 작은 LNR 수열

$n$비트 시프트 레지스터는 $n$개의 비트를 저장하는 장치이고, 저장된 내용을 바꾸는 방법은 두 가지뿐이다. 내용을 왼쪽으로 한 칸 밀어낸 다음, 비어 있는 가장 오른쪽 자리에 0이나 1을 넣는다. 이렇게 한 번 바꾸는 것을 이동이라고 부른다. 예를 들어 4비트 시프트 레지스터의 내용이 0001일 때 이동을 한 번 하면 내용은 0010(오른쪽 끝에 0을 넣은 경우)이나 0011(1을 넣은 경우)이 된다.

내용이 모두 0인 $n$비트 시프트 레지스터에서 시작한다. 이동할 때마다 레지스터의 내용이 지금까지 나온 모든 내용과 달라지도록 이동을 이어 나가야 한다. $n$비트 시프트 레지스터가 가질 수 있는 내용은 $2^n$가지이므로 이런 이동 열의 길이는 최대 $2^n$이다. 어떤 $n$에 대해서도 길이가 $2^n$인 열이 하나 이상 존재한다는 사실이 알려져 있다. $n = 3$일 때는 길이가 $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) 수열

양의 정수 $n$에 대해 다음 다섯 조건을 모두 만족하는 수열을 생각하자.

1. 수열의 각 원소는 길이가 $n$인 비트 문자열이다.
2. 수열의 원소는 $2^n$개이다.
3. 같은 원소가 두 번 나오지 않는다.
4. 첫 번째 원소의 $n$개 비트는 모두 0이다.
5. 첫 번째를 제외한 각 원소는 바로 앞 원소에서 위에서 설명한 이동 한 번으로 얻는다.

이런 수열을 Longest-Non-Repeating 수열, 줄여서 LNR 수열이라고 부른다. 양의 정수 $n$에 대해 위 다섯 조건을 만족하는 LNR 수열 전체의 집합을 $S(n)$으로 쓴다.

가장 작은 LNR 수열

LNR 수열 $s \in S(n)$에는 다음과 같이 값 $value(s)$를 정한다. $s$의 비트 문자열 $2^n$개를 순서대로 이어 붙여 하나의 비트 문자열을 만들고, 이 문자열을 이진수로 읽은 값이 $value(s)$이다. 위에서 본 LNR 수열 $A$에 대해서는 다음과 같다.

$value(A)$ = 000001010101011111110100

가장 작은 LNR 수열 $s_{small}(n)$은 $S(n)$에 속한 수열 중 $value(s)$가 가장 작은 수열이다. $n = 3$일 때 LNR 수열은 앞에서 본 $A$와 $B$ 두 개뿐이고 $value(A) < value(B)$이므로 $s_{small}(3) = A$이다. $A$에서 비트 문자열 000, 001, 010, 101, 011, 111, 110, 100의 위치는 차례로 1, 2, 3, 4, 5, 6, 7, 8이다.

해야 할 일

양의 정수 $n \le 10$과 길이가 $n$인 비트 문자열 $s$가 주어지면 $s_{small}(n)$을 구해서 그 안에서 $s$가 몇 번째 원소인지 출력하라. $s$가 $s_{small}(n)$의 첫 번째 원소이면 1을, 두 번째 원소이면 2를 출력한다.

입력은 두 줄이다. 첫째 줄에 양의 정수 $n \le 10$이 주어진다. 둘째 줄에 길이가 $n$인 비트 문자열 $s$가 주어진다.

$s_{small}(n)$에서 $s$의 위치를 나타내는 양의 정수 하나를 출력한다.

LNR 수열을 모두 만든 다음 그중에서 가장 작은 것을 고르려고 하지 마라. 이동을 고를 때 0을 밀어 넣는 이동을 1을 밀어 넣는 이동보다 먼저 시도하면 가장 작은 LNR 수열을 찾을 수 있다.