平面上有一组点 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