순열

시간 제한1초메모리 제한512 MB

요약

점 N개를 한 줄로 나열하는 순열 중, 네 번째 점부터 이전 점과 교차하지 않는 선분을 정확히 세 개씩 그리는 경우의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 동적 계획법
정답자: 아직 제출이 없습니다

문제

베시는 2차원 격자 위에 좋아하는 서로 다른 점 $N$ 개를 가지고 있다( $3\le N\le 40$ ). 어느 세 점도 한 직선 위에 있지 않다. 각 $1\le i\le N$ 에 대해 $i$ 번째 점은 두 정수 $x_i$ , $y_i$ 로 나타낸다( $0\le x_i,y_i\le 10^4$ ).

베시는 다음 방법으로 점들 사이에 선분을 긋는다.

$N$ 개 점의 순열 $p_1,p_2,\ldots,p_N$ 을 고른다.
$p_1$ 과 $p_2$ , $p_2$ 와 $p_3$ , $p_3$ 과 $p_1$ 사이에 선분을 긋는다.
그다음 $i$ 가 4부터 $N$ 까지 순서대로, $p_i$ 에서 $i$ 보다 작은 모든 $j$ 에 대해 $p_j$ 까지 선분을 긋는다. 단, 이미 그은 선분과 (끝점을 제외하고) 교차하지 않는 경우에만 긋는다.

베시는 각 $i$ 마다 새 선분을 정확히 3개씩 그었다는 사실을 확인했다. 이 성질을 만족하도록 1단계에서 베시가 고를 수 있었던 순열의 개수를 구하라. 답은 $10^9+7$ 로 나눈 나머지로 출력한다.

입력

첫째 줄에 $N$ 이 주어진다.

이어서 $N$ 개의 줄에 각각 공백으로 구분된 두 정수 $x_i$ 와 $y_i$ 가 주어진다.

출력

순열의 개수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
4
0 0
0 4
1 1
1 2
```
예상 출력
```
0
```
예제 2
입력
```
4
0 0
0 4
4 0
1 1
```
예상 출력
```
24
```
예제 3
입력
```
5
0 0
0 4
4 0
1 1
1 2
```
예상 출력
```
96
```