컴퓨터 변환

시간 제한1초메모리 제한128 MB

요약

이 문자열은 각 0을 10으로, 각 1을 01로 바꾸는 규칙(토마스-모스 수열)을 n번 적용한 뒤 연속된 두 0이 몇 번 나오는지 큰 수로 구하는 문제입니다.

문제

컴퓨터에 처음에는 한 자리 숫자 $1$ 하나로 이루어진 수열이 저장되어 있다. 매 시간 단계마다 컴퓨터는 모든 숫자 $0$ 을 수열 $1\,0$ 으로, 모든 숫자 $1$ 을 수열 $0\,1$ 로 동시에 바꾼다.

따라서 첫 번째 단계 후에는 수열 $0\,1$ 이 되고, 두 번째 단계 후에는 $1\,0\,0\,1$ , 세 번째 단계 후에는 $0\,1\,1\,0\,1\,0\,0\,1$ 이 되며, 이런 식으로 계속된다.

$n$ 단계 후의 수열에는 연속한 두 개의 $0$ (즉 $0\,0$ ) 쌍이 몇 개 나타나는가?

입력의 각 줄에는 자연수 $n$ ( $0 < n \le 1000$ )이 하나씩 주어진다. 입력의 끝까지 각 줄을 처리한다.

각 $n$ 에 대해, $n$ 단계 후의 수열에 나타나는 연속한 $0$ 쌍의 개수를 한 줄에 하나씩 출력한다.