#D8518. Drawing Circles is Fun
Drawing Circles is Fun
Drawing Circles is Fun
There are a set of points S on the plane. This set doesn't contain the origin O(0, 0), and for each two distinct points in the set A and B, the triangle OAB has strictly positive area.
Consider a set of pairs of points (P1, P2), (P3, P4), ..., (P2k - 1, P2k). We'll call the set good if and only if:
- k ≥ 2.
- All Pi are distinct, and each Pi is an element of S.
- For any two pairs (P2i - 1, P2i) and (P2j - 1, P2j), the circumcircles of triangles OP2i - 1P2j - 1 and OP2iP2j have a single common point, and the circumcircle of triangles OP2i - 1P2j and OP2iP2j - 1 have a single common point.
Calculate the number of good sets of pairs modulo 1000000007 (109 + 7).
Input
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of points in S. Each of the next n lines contains four integers ai, bi, ci, di (0 ≤ |ai|, |ci| ≤ 50; 1 ≤ bi, di ≤ 50; (ai, ci) ≠ (0, 0)). These integers represent a point .
No two points coincide.
Output
Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).
Examples
Input
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
Output
2
Input
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
Output
4
Input
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
Output
10
inputFormat
Input
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of points in S. Each of the next n lines contains four integers ai, bi, ci, di (0 ≤ |ai|, |ci| ≤ 50; 1 ≤ bi, di ≤ 50; (ai, ci) ≠ (0, 0)). These integers represent a point .
No two points coincide.
outputFormat
Output
Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).
Examples
Input
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
Output
2
Input
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
Output
4
Input
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
Output
10
样例
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
4