#P18545. All the Way Left
All the Way Left
All the Way Left
小喝粥(Little Drink Congee)是小青鱼(Little Cyan Fish)的好朋友,也是著名表演团体 All the Way Left 的成员。他最近正在练习在舞台上辨别方向的能力。
舞台可以看作二维笛卡尔平面。他选择了 个互不相同的点 ,其中 。他希望按照顺序 经过所有这些点。一次遍历是长度为 的排列 ,其中从 到 连接一条有向线段。
当且仅当同时满足以下条件,这次遍历是好的:
- 路径不自交。 任意两条线段不能相交;唯一允许的例外是两条相邻线段在它们共同的一个端点处相交。
- 对每个 ,第 次转向都是左转或直行。形式化地,向量 与 的叉积非负。
小喝粥希望知道好的遍历共有多少种,答案对 取模。但他还要陪伴小青鱼,没有时间解决这个问题,请你帮助他。
输入格式
第一行包含整数 (),表示测试用例数。
对于每个测试用例:
- 第一行包含整数 ()。
- 接下来 行,第 行包含两个整数 (),表示点 的坐标。
保证每个测试用例中所有点的坐标两两不同。
保证一个输入文件中所有测试用例的 之和不超过 。
输出格式
每个测试用例输出一行,一个整数,表示好的遍历数对 取模的结果。
原样例
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
原题没有额外样例说明。题目没有保证任意三点不共线;相邻线段的共线反向重叠、非相邻线段的端点接触或重叠都不属于允许的例外。