06667. USACO·三角形排列 未做

Bessie 在二维平面上有 $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$）。

Bessie 按如下方式在这些点之间画一些线段：

• 她选择这 $N$ 个点的某个排列 $p_1,p_2,\dots ,p_N$。
• 她在点 $p_1$ 和 $p_2$、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
• 然后依次对于从 $4$ 到 $N$ 的每个整数 $i$，对于所有 $j<i$，她从 $p_i$ 到 $p_j$ 画上一条线段，只要这条线段不与任何已经画上的线段相交（端点位置相交除外）。

Bessie 注意到对于每一个 $i$，她都画上了恰好三条新的线段。计算 Bessie 在第 1 步可以选择的满足上述性质的排列的数量，结果对 $10^9+7$ 取模。

输入的第一行包含 $N$。

以下 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。

输出排列的数量模 $10^9+7$ 的结果。

【样例解释】

一个满足该性质的排列为 $(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)$ 以某种顺序排列，则此排列不满足该性质。

• 测试点 7-20 没有额外限制。

【数据规模与约定】

• 测试点 1-6 满足 $N\le 8$。

• 测试点 7-20 没有额外限制。

供题：Benjamin Qi