Triangles made from lines
InterviewTime limit1sMemory limit128 MB
Count how many triples of the given lines form a triangle by removing triples that contain parallel lines.
- Level
Medium4 of 10
- Topics
- Hash map, Combinatorics, Math
- Solved
- No attempts yet
Problem
Sanggeun has lines on the coordinate plane. The th line is written as .
Write a program that counts the triangles you can build by picking three of his lines.

No three lines meet at one point.
Input
The first line contains the number of lines . ()
Each of the next lines contains , , of the th line. Every number is an integer whose absolute value is at most , and no line has and both equal to 0.
Output
Print the number of triangles the given lines build. The count can be very large, so print it modulo 1,000,000,007.