레이팅 미적용베시는 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\)까지 순서대로 보면서, 새 선분이 이전에 그린 어떤 선분과도 (끝점을 제외하고) 교차하지 않는 모든 \(j
베시는 각 \(i\)마다 정확히 세 개의 새로운 선분을 그렸다는 것을 알아차렸다. 이 성질이 성립하도록 1단계에서 베시가 선택할 수 있었던 순열의 개수를 \(10^9+7\)로 나눈 나머지를 구하시오.
출제자: Benjamin Qi
채점 방식
- 테스트 케이스 1-6은 \(N\le 8\)을 만족한다.
- 테스트 케이스 7-20은 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 걸쳐 각 줄에 공백으로 구분된 두 정수 \(x_i\)와 \(y_i\)가 주어진다.
순열의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.
4
0 0
0 4
1 1
1 20No permutations work.
4
0 0
0 4
4 0
1 124All permutations work.
5
0 0
0 4
4 0
1 1
1 296One permutation that satisfies the property is \((0,0),(0,4),(4,0),(1,2),(1,1).\)
For this permutation,
- First, she draws segments between every pair of \((0,0),(0,4),\) and \((4,0)\).
- Then she draws segments from \((0,0),\) \((0,4),\) and \((4,0)\) to \((1,2)\).
- Finally, she draws segments from \((1,2),\) \((4,0),\) and \((0,0)\) to \((1,1)\).
Diagram:
The permutation does not satisfy the property if its first four points are
\((0,0)\), \((1,1)\), \((1,2)\), and \((0,4)\) in some order.