Bessie 在二维平面上有 $N$ 个最爱的不同的点，其中任意三点均不共线。对于每一个 $1 \leqslant i \leqslant N$，第 $i$ 个点可以用两个整数 $x_i$ 和 $y_i$ 表示。

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

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

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

• $3 \leqslant N \leqslant 40$
• $0 \leqslant x_i,y_i \leqslant 10^4$

输入格式

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

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

输出格式

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

4
0 0
0 4
1 1
1 2

0

没有排列满足该性质。

4
0 0
0 4
4 0
1 1

24

所有排列均满足该性质。

5
0 0
0 4
4 0
1 1
1 2

96

一个满足该性质的排列为 $(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 \leqslant 8$。
• 测试点 7-20 没有额外限制。

题目提供者

Benjamin Qi