Little Drink Congee 是 Little Cyan Fish 的好朋友，也是著名表演团体 All the Way Left 的成员。他最近一直在练习在舞台上辨别方向的能力。为了练习，他在舞台上选了 $n$ 个不同的点 $A_1, A_2, \dots, A_n$。舞台被表示为一个二维笛卡尔坐标系，其中第 $i$ 个点位于坐标 $(x_i, y_i)$。Little Drink Congee 想要按照 $p_1, p_2, \dots, p_n$ 的顺序经过所有这些点。遍历是一个长度为 $n$ 的排列 $p$，其中每个点 $A_{p_i}$ 都通过一条有向线段连接到 $A_{p_{i+1}}$。

Little Drink Congee 认为一个遍历是“好的”，当且仅当满足以下条件：

• 它是不自相交的，即除了相邻线段在公共端点处相交外，没有两条线段相交。
• 对于每个 $1 \le i \le n - 2$，第 $i$ 次转向是向左的（或直行）。形式上，向量 $\vec{A_{p_i}A_{p_{i+1}}}$ 和 $\vec{A_{p_{i+1}}A_{p_{i+2}}}$ 的叉积是非负的。

Little Drink Congee 想知道“好的”遍历的数量，结果对 $(10^9 + 7)$ 取模。然而，他需要花时间陪伴 Little Cyan Fish，无法自己解决这个挑战。请帮他计算一下！

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^3$)。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 10^9$)，表示点 $A_i$ 的坐标。所有点的坐标各不相同。 保证所有测试用例的 $n^2$ 之和不超过 $4 \times 10^6$。

输出格式

对于每个测试用例，输出一行，包含“好的”遍历的数量，结果对 $(10^9 + 7)$ 取模。

样例

输入 1

3
4
1 1
3 1
2 2
2 3
3
1 1
1 2
1 3
6
1 1
2 1
2 2
2 3
3 2
4 2

输出 1

6
2
13