题目描述

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

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

• 1. 她选择这 $N$ 个点的某个排列 $p_1,p_2,\dots,p_N$ 。
• 2. 她在点 $p_1$ 和 $p_2$ 、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
• 3. 然后依次对于从 $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$ 取模后的结果。

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)$ 画上线段。

数据范围与约定

$3\le N \le 40$，$0\le x_i,y_i \le 10^4$