小喝粥是小青鱼的好朋友，也是著名演艺团体一路向左的成员。最近，他一直在练习识别舞台上的方向能力。为了练习，他在舞台上选定了 $n$ 个不同的点 $A_1, A_2, \cdots, A_n$。舞台被表示为一个二维笛卡尔平面，其中第 $i$ 个点位于坐标 $(x_i, y_i)$ 处。小喝粥的目标是按顺序 $p_1, p_2, \cdots, p_n$ 遍历所有这些点。一次遍历是一个长度为 $n$ 的排列 $p$，其中每个点 $A_{p_i}$ 通过一个有向线段连接到 $A_{p_{i+1}}$。

小喝粥认为，只有当以下条件成立时，一次遍历才被认为是好的：

• 它是不自交的。也就是除了相邻的两条线段会在端点处相交，其他的都是不交的。
• 这条折线只会左转，或者直行。即对于所有 $1\leq i \leq n-2$，$\overrightarrow{A_{p_i}A_{p_{i+1}}}$ 和 $\overrightarrow{A_{p_{i+1}}A_{p_{i+2}}}$ 的叉积，是非负的。

小喝粥想知道好的遍历数目对 $(10^9 + 7)$ 取模后的结果。然而，他需要和小青鱼在一起摸鱼，无法自己解决这个挑战。请你帮助他计算！

输入格式

第一行包含一个正整数 $T$ ($1\leq T \leq 10^4$)，表示数据组数。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \leq n \leq 2 \times 10^3$)。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $x_i$ 与 $y_i$ ($1 \leq x_i, y_i \leq 10^9$)，表示 $A_i$ 的坐标，保证所有点的坐标两两不同。

保证所有测试数据中的 $n^2$ 之和不超过 $4 \times 10^6$。

输出格式

对于每组测试数据，输出一行一个数，表示满足条件的折线个数取模 $(10^9 + 7)$。

样例数据

input

15
1
1 1
2
1 1
1 2
3
1 1
1 2
1 3
3
1 1
1 2
2 2
5
1 1
1 3
2 2
3 1
3 3
6
1 1
1 3
2 2
3 2
4 1
4 3
6
1 3
2 1
2 2
2 3
2 4
3 2
6
1 1
5 1
3 5
2 2
4 2
3 3
7
1 1
5 1
2 2
3 2
4 2
3 3
3 4
6
2 10
8 9
2 3
2 5
3 5
2 6
10
1 10
7 6
8 4
3 8
6 9
3 7
6 8
8 5
10 9
8 8
8
1 1
2 3
2 4
1 6
5 3
5 4
6 1
6 6
8
1 1
2 3
3 3
4 2
4 4
5 1
1 5
5 5
5
1 1
2 999999998
2 999999999
2 1000000000
3 1
6
1 1
1 1000000000
1000000000 1
1000000000 1000000000
999999999 999999998
999999998 999999997

output

1
2
2
3
8
14
12
16
22
10
54
32
28
10
14

子任务

子任务一（7 分）

没有额外的限制。