극장 좌석 배치 2 timer 1s memory 256MB

극장에 N 개의 빈 좌석이 있다.

K 명의 관객들이 영화를 보기 위해서 왔다.

이 관객들이  N​ 개의 좌석에 앉을 수 있는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

(단, K​ 명의 사람을 서로 구분되지 않으며, 한 명이 좌석에 앉으면 

그 왼쪽이나 오른쪽 중 적어도 하나는 비어 있도록 배치해야 한다.)