U158675 [USACO21OPEN] Permutation G
题目背景
题目来源：USACO 2021 Open Gold Problem 3
题目描述
Bessie 在二维平面上有 $N$（$3≤N≤40$）个最爱的不同的点，其中任意三点均不共线。对于每一个 $1≤i≤N$，第 $i$ 个点可以用两个整数 $x_i$ 和 $y_i$ 表示（$0≤x_i$,$y_i≤10^4$）。
Bessie 按如下方式在这些点之间画一些线段：
1. 她选择这 $N$ 个点的某个排列 $p_1,p_2,…,p_N$。
2. 她在点 $p_1$ 和 $p_2$、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
3. 然后依次对于从 $4$ 到 $N$ 的每个整数 $i$，对于所有 $j
输入格式
输入的第一行包含 $N$。
以下 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。
输出格式
输出排列的数量模 $10^9+7$ 的结果。
说明/提示
样例1:
没有排列满足该性质。
样例2:
所有排列均满足该性质。
样例3:
一个满足该性质的排列为 $(0,0),(0,4),(4,0),(1,2),(1,1)$。对于这个排列，
- 首先，她在 $(0,0)$, $(0,4)$ 和 $(4,0)$ 两两之间画上线段。
- 然后她从 $(1,2)$ 向 $(0,0)$, $(0,4)$ 和 $(4,0)$ 画上线段。
- 最后，她从 $(1,1)$ 向 $(1,2)$, $(4,0)$ 和 $(0,0)$ 画上线段。
如图：
如果排列的前四个点是 $(0,0)$、$(1,1)$、$(1,2)$ 和 $(0,4)$ 以某种顺序排列，则此排列不满足该性质。
测试点性质：
- 测试点 1-6 满足 $N≤8$。
- 测试点 7-20 没有额外限制。