주차 칸 배정

한 주차장에는 1번부터 N번까지 번호가 붙은 주차 칸이 한 줄로 늘어서 있다. 오늘 이 주차장에는 1번부터 N번까지 번호가 붙은 차 N대가 들어오며, 한 칸에는 차 한 대만 들어간다. 따라서 모든 칸이 꼭 한 대씩 채워진다.

차는 자기 번호와 같은 칸에 들어가는 것이 원칙이지만 바로 옆 칸이라면 들어가도 된다. 즉 K번 차는 K-1번 칸, K번 칸, K+1번 칸 가운데 하나를 쓸 수 있다. 1번 차는 왼쪽에 칸이 없으므로 1번 칸과 2번 칸만 쓸 수 있고, N번 차도 같은 이유로 N-1번 칸과 N번 칸만 쓸 수 있다.

그런데 M개의 칸에는 충전기가 달려 있다. 충전기가 달린 칸은 그 칸의 번호와 같은 번호의 차만 쓸 수 있다. 예를 들어 4번 칸에 충전기가 달려 있다면 4번 차는 반드시 4번 칸에 들어가야 하고, 다른 차는 4번 칸을 쓸 수 없다.

N대의 차를 모두 주차하는 방법이 몇 가지인지 계산하는 프로그램을 작성하여라.

예를 들어 N=9이고, 충전기가 달린 칸이 4번 칸과 7번 칸이라고 해보자. 칸의 상태를 표로 적으면 다음과 같다.

4번 차와 7번 차의 자리가 먼저 정해지므로, 남은 칸은 충전 칸을 경계로 세 묶음으로 끊어진다. 각 묶음에 속한 차들은 그 묶음을 벗어날 수 없다. 묶음마다 가능한 방법의 수를 세어 정리하면 다음과 같다.

세 칸이 이어진 묶음에서는 세 대가 모두 자기 칸에 들어가는 방법, 앞의 두 대가 자리를 맞바꾸는 방법, 뒤의 두 대가 자리를 맞바꾸는 방법으로 3가지가 나온다. 두 칸이 이어진 묶음에서는 그대로 들어가는 방법과 맞바꾸는 방법으로 2가지가 나온다.

세 묶음은 서로 영향을 주지 않으므로 전체 방법의 수는 각 묶음의 방법의 수를 모두 곱한 값이다. 따라서 현재 예시에서의 정답은 3 × 2 × 2 = 12다.

충전기가 달린 칸이 하나도 없는 경우도 있다. 이때는 칸이 끊어지지 않고 1번부터 N번까지 한 묶음으로 이어진다. 반대로 충전 칸이 1번 칸이나 N번 칸인 경우도 있다. 이때는 그 바깥쪽에 칸이 없으므로 묶음이 하나 줄어든다.

입출력 예시

예시 1

입력

9
2
4
7

출력

12

예시 2

입력

9
3
2
4
7

출력

4

예시 3

입력

40
0

출력

165580141