자리 배치
시간 제한2초메모리 제한128 MB
자유석 하나를 포함한 N개의 좌석에서, 각 사람이 자기 지정석, 그 옆자리, 또는 자유석에만 앉을 수 있도록 하는 배치 방법의 수를 구합니다.
문제
어떤 극장의 좌석은 한 줄로 놓여 있으며, 왼쪽부터 오른쪽까지 1번부터 N번까지 번호가 붙어 있다. 이 N개의 좌석 중 N-1개는 지정석 표로 판매되고, 나머지 한 좌석은 자유석으로 정해진다. 지정석 표를 가진 사람은 다음 규칙에 따라 앉을 수 있다.
- 자기 표에 적힌 번호의 좌석에 앉을 수 있다.
- 그 좌석의 바로 왼쪽이나 바로 오른쪽에 있는 좌석에 앉을 수 있다.
- 자유석에 앉을 수 있다.
예를 들어 좌석이 4개인 극장에서 1번, 2번, 4번 좌석은 지정석으로 판매되고 3번 좌석이 자유석이라고 하자. 아래 그림에서 회색 좌석이 자유석이다.
그림 1
아래 그림에서 번호 i는 i번 지정석 표를 가진 사람을 나타낸다. 그림 2의 (a), (b), (c), (d)는 위 규칙을 만족하는 자리 배치이다.
그림 2
다음 네 가지 배치는 규칙을 만족하지 않는다.
그림 3
그림 3(a)는 4번 지정석 표를 가진 사람이 앉지 않았기 때문에 올바르지 않다. 그림 3(b), (c), (d)는 1번 또는 4번 지정석 표를 가진 사람이 자기 좌석에서 두 칸 이상 떨어진 좌석에 앉았기 때문에 올바르지 않다.
전체 좌석 수 N과 자유석 번호 K가 주어질 때, 위 규칙을 만족하는 자리 배치의 수를 구하라.
입력
첫째 줄에 좌석 수 N이 주어진다. (3 ≤ N ≤ 40)
둘째 줄에 자유석 번호 K가 주어진다. (1 ≤ K ≤ N)
출력
규칙을 만족하는 자리 배치의 수를 첫째 줄에 출력한다. 이 값은 2^31 - 1 이하의 정수이다.