Under construction

Still being built. Things may change

Triangles made from lines

Interview

Time limit1sMemory limit128 MB

Summary
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 NN lines on the coordinate plane. The iith line is written as Aix+Biy+Ci=0A_i x + B_i y + C_i = 0.

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 NN. (1≤N≤300,0001 \le N \le 300{,}000)

Each of the next NN lines contains AiA_i, BiB_i, CiC_i of the iith line. Every number is an integer whose absolute value is at most 10910^9, and no line has AiA_i and BiB_i 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.

Examples2

  1. Example 1

    Input
    6
    0 1 0
    -5 3 0
    -5 -2 25
    0 1 -3
    0 1 -2
    -4 -5 29
    
    Expected output
    10
    
  2. Example 2

    Input
    5
    -5 3 0
    -5 -3 -30
    0 1 0
    3 7 35
    1 -2 -1
    
    Expected output
    10