어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1 번부터 N번까지 번호가 매겨져 있다.
공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.
예를 들어서, 입장권에 5 번이 써 있으면 5 번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7 번 입장권을 가진 사람은 7 번 좌석은 물론이고, 6 번 좌석이나 8 번 좌석에도 앉을 수 있다. 그러나 5 번 좌석이나 9 번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “고정석 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
오늘 공연은 입장권이 매진되어 1 번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. 고정석 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.
예를 들어서, 그림과 같이 좌석이 9 개이고, 4 번 좌석과 7 번 좌석이 고정석인 경우 가능한 경우와 가능하지 않는 경우의 몇가지 예이다.
1 2 3 4 5 6 7 8 9 좌석번호1 2 3 4 5 6 7 8 9(o) 2 1 3 4 6 5 7 8 9(o) 3 1 2 4 5 6 7 8 9(x) 1 2 3 5 4 6 7 8 9(x)
입력 9 2 4 7 출력 12
출처:koi 초등 기출