#P18545. All the Way Left

All the Way Left

All the Way Left

小喝粥(Little Drink Congee)是小青鱼(Little Cyan Fish)的好朋友,也是著名表演团体 All the Way Left 的成员。他最近正在练习在舞台上辨别方向的能力。

舞台可以看作二维笛卡尔平面。他选择了 nn 个互不相同的点 A1,A2,…,AnA_1,A_2,\ldots,A_n,其中 Ai=(xi,yi)A_i=(x_i,y_i)。他希望按照顺序 p1,p2,…,pnp_1,p_2,\ldots,p_n 经过所有这些点。一次遍历是长度为 nn 的排列 pp,其中从 ApiA_{p_i} 到 Api+1A_{p_{i+1}} 连接一条有向线段。

当且仅当同时满足以下条件,这次遍历是好的:

  • 路径不自交。 任意两条线段不能相交;唯一允许的例外是两条相邻线段在它们共同的一个端点处相交。
  • 对每个 1≤i≤n−21\le i\le n-2,第 ii 次转向都是左转或直行。形式化地,向量 ApiApi+1→\overrightarrow{A_{p_i}A_{p_{i+1}}} 与 Api+1Api+2→\overrightarrow{A_{p_{i+1}}A_{p_{i+2}}} 的叉积非负。

小喝粥希望知道好的遍历共有多少种,答案对 109+710^9+7 取模。但他还要陪伴小青鱼,没有时间解决这个问题,请你帮助他。

输入格式

第一行包含整数 TT(1≤T≤1041\le T\le10^4),表示测试用例数。

对于每个测试用例:

  • 第一行包含整数 nn(1≤n≤20001\le n\le2000)。
  • 接下来 nn 行,第 ii 行包含两个整数 xi,yix_i,y_i(1≤xi,yi≤1091\le x_i,y_i\le10^9),表示点 AiA_i 的坐标。

保证每个测试用例中所有点的坐标两两不同。

保证一个输入文件中所有测试用例的 n2n^2 之和不超过 4×1064\times10^6。

输出格式

每个测试用例输出一行,一个整数,表示好的遍历数对 109+710^9+7 取模的结果。

原样例

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
6
2
13

原题没有额外样例说明。题目没有保证任意三点不共线;相邻线段的共线反向重叠、非相邻线段的端点接触或重叠都不属于允许的例外。