어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다.

이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 비워둔다.

지정석 표를 산 사람들은 아래 규칙에 따라서만 앉을 수 있다.

규칙) 사람들은 구입한 지정석 표에 적힌 번호의 자리에 앉든지,
그 자리의 바로 왼쪽이나 오른쪽의 인접한 자리에 앉든지, 또는 자유석에 앉을 수 있다.

예를 들어 설명해보자. 4개의 자리가 있는 극장의 경우,
아래 그림1과 같이 1, 2, 4번 자리는 지정석으로 판매되었고, 3번 자리는 자유석(회색으로 표시)으로 지정되었다.

아래 그림에서 ⓘ는 지정석 표의 번호가 i인 사람을 나타낸다.

그림2의 (a), (b), (c), (d)는 위의 규칙을 만족하는 자리배치의 예이다.

다음 4가지 경우는 위의 규칙을 만족하지 않는 자리배치의 예이다.

그림3의 (a)는 4번 좌석표를 받은 사람이 자리에 앉지 않았기 때문에 규칙에 어긋난 자리배치이다.

그림3 (b), (c), (d)의 경우에는 1번 혹은 4번 좌석표를 받은 사람이 원래 자리에서 2칸 이상 떨어진 자리에 앉아서 규칙에 어긋난 경우이다.

문제는 전체 자리의 수 N이 주어지고, 자유석 번호 K가 주어져 있을 때,
앞서 말한 규칙을 만족하며 배치할 수 있는 모든 경우의 수를 출력하는 것이다.

자리 배치 timer 1s memory 64MB

자리 배치 1s 64MB