시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 3 3 37.500%

문제

도현이는 종이에 점 N개를 찍어서 정 N각형을 만들었다. 정점은 1번부터 N번까지 시계 방향으로 매겨져 있다.

그 다음, 직선을 총 M-1개 그렸다. 직선은 도현이가 그린 다각형의 꼭지점을 연속해서 연결해서 그렸으며, 그 순서는 Pi로 나타낸다. 즉, P0번과 P1번을 연결하고, P1번과 P2번을, ..., PM-2번과 PM-1번을 연결했다.

이제, 모든 꼭지점을 한 번씩 방문하고, P0으로 다시 돌아오는 경로를 만들어 보려고 한다. 즉, 남은 꼭지점을 방문한 순서를 Ti라고 했을 때, PM-1과 T0을 연결하고, T0과 T1을, ..., TN-M-1과 P0을 연결해야 한다.

시작점 (P0)을 제외한 모든 꼭지점은 한 번씩 방문해야 하며, P에 포함되어 있는 꼭지점과 T에 포함되어 있는 꼭지점은 겹치면 안된다. 또, 새로운 꼭지점을 연결할 때는 이전에 그린 선분과 교차하게 그려야 한다. 이 때, 교차는 P에서 그린 선분과 새로 그린 선분 모두를 포함한다.

N과 M, 그리고 P가 주어졌을 때, 가능한 T의 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어지고, 둘째 줄에 Pi가 P0부터 순서대로 주어진다. (4 ≤ N ≤ 18, 2 ≤ M ≤ N-1)

출력

첫째 줄에 가능한 T의 방법의 수를 출력한다.

예제 입력 1

5 3
1 3 5

예제 출력 1

1

예제 입력 2

6 3
1 4 2

예제 출력 2

1

예제 입력 3

7 3
2 4 7

예제 출력 3

2

예제 입력 4

7 6
1 2 3 4 6 5

예제 출력 4

0

힌트

예제 1의 경우, 가능한 방법은 1개이다. (1 -> 3 -> 5 -> 2 -> 4)

예제 2의 경우에 가능한 T는 (6, 3, 5, 1) 이다.

예제 3의 경우에는 (3, 5, 1, 6, 2)와 (3, 6, 1, 5, 2)가 가능하다.

출처