3005: Drawing Circles is Fun
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
time limit per test
3 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputThere 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