← 返回题目列表

Codeforces · 372/E

E. 画圆圈很有趣

中文机器翻译题面 查看原题

平面上有一组点 S。该集合不包含原点 O(0, 0),并且对于集合 A 和 B 中的每两个不同点,三角形 OAB 的面积严格为正。

考虑一组点对 (P1, P2), (P3, P4), ..., (P2k - 1, P2k)。当且仅当满足以下条件时,我们才称该集合为好集合:

- k ≥ 2。
- 所有 Pi 都是不同的,并且每个 Pi 都是 S 的一个元素。
- 对于任意两对 (P2i - 1, P2i) 和 (P2j - 1, P2j),三角形 OP2i - 1P2j - 1 和 OP2iP2j 的外接圆有一个公共点,并且三角形的外接圆OP2i - 1P2j 和 OP2iP2j - 1 有一个公共点。

计算模 1000000007 (109 + 7) 的良好配对组数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1000) — S 中的点数。接下来的 n 行每行包含四个整数 ai, bi, ci, di (0 ≤ |ai|, |ci| ≤ 50; 1 ≤ bi, di ≤ 50;(ai, ci) ≠ (0, 0))。这些整数代表一个点$$(\frac{a_i}{b_i}, \frac{c_i}{d_i})$$。

没有两点重合。

输出

打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

10
-46 46 0 36
0 20 -24 48
-50 50 -49 49
-20 50 8 40
-15 30 14 28
4 10 -4 5
6 15 8 10
-20 50 -3 15
4 34 -16 34
16 34 2 17

输出 #1

2

输入 #2

10
30 30 -26 26
0 15 -36 36
-28 28 -34 34
10 10 0 4
-8 20 40 50
9 45 12 30
6 15 7 35
36 45 -8 20
-16 34 -4 34
4 34 8 17

输出 #2

4

输入 #3

10
0 20 38 38
-30 30 -13 13
-11 11 16 16
30 30 0 37
6 30 -4 10
6 15 12 15
-4 5 -10 25
-16 20 4 10
8 17 -2 17
16 34 2 17

输出 #3

10