Less Coin Tosses

Carla와 Daniel은 오늘 누가 설거지를 할지 정하기 위해 동전 던지기를 하기로 했다. Carla의 수집품에 있는 오래된 동전 중 하나를 사용한다. Daniel은 이 때문에 걱정이 된다. 이 동전들은 휘어 있고 균형이 맞지 않아서, 동전을 던질 때 앞면과 뒷면이 나올 확률이 반드시 같지는 않기 때문이다.

Carla는 자신의 동전을 잘 알고 있어서, 이길 확률이 가장 높은 동전을 고를 수 있다. 그래서 Daniel은 어떤 동전을 골라도 게임이 완전히 공정해지는 방법을 생각해 냈다. 먼저, 각자에게 크기 N인 이진 문자열의 공집합이 아닌 집합을 하나씩 배정한다. 같은 문자열이 두 집합에 모두 속할 수는 없고, 어느 집합에도 포함되지 않는 문자열이 있어도 된다. 예를 들어 N = 3일 때 문자열을 배정하는 유효한 방법 하나는 다음과 같다.

• "010"과 "110"은 Carla의 것;
• "001"과 "011"은 Daniel의 것;
• "000", "100", "101", "111"은 둘 다의 것도 아니다.

문자열을 배정한 뒤, Carla와 Daniel은 같은 동전을 N번 던지고 결과의 나열을 적는다. 앞면은 0, 뒷면은 1로 한다. 나온 이진 문자열이 Carla의 집합에 속하면 그녀가 이긴다. Daniel의 집합에 속하면 그가 이긴다. 어느 쪽에도 속하지 않으면, 새로운 문자열을 얻기 위해 동전을 N번 더 던진다. 승자가 나올 때까지 이 과정을 필요한 만큼 반복한다.

이 방법이 제대로 작동하려면 Carla와 Daniel 사이의 문자열 배정 방식이 중요하다. Carla의 집합에 속한 문자열이 생성될 확률과 Daniel의 집합에 속한 문자열이 생성될 확률이 같아야 한다. 다시 말해, 길이 N인 이진 문자열 S가 균형이 맞지 않을 수도 있는 같은 동전을 N번 던져 생성될 확률을 P(S)라고 하자. Carla의 집합에 있는 모든 문자열의 P 합은 Daniel의 집합에 있는 모든 문자열의 P 합과 같아야 한다.

문자열을 공정하게 배정하는 것과 더불어, Carla와 Daniel은 동전 던지기를 되풀이하는 일을 최대한 피하고 싶어 하므로, 어느 집합에도 속하지 않는 문자열의 수를 최소로 하려고 한다. N이 주어졌을 때, 배정되지 않는 이진 문자열의 최소 개수를 구하여라.

입력은 한 줄로 이루어지며, 정수 N이 주어진다. N은 동전을 던지는 횟수이자 이진 문자열의 크기이다 (2 ≤ N ≤ 1018).

프로그램은 한 줄에 정수 하나를 출력해야 한다. 이는 배정되지 않는 이진 문자열의 최소 개수이다.