Description

Given $N$ lines in the Cartesian coordinate plane. Points on these lines satisfy $A_i x + B_i y + C_i = 0$.

Please find the number of triangles formed by these lines. Output the answer modulo $10^9+7$.

It is guaranteed that no three lines intersect at the same point.

Input Format

The first line contains an integer $N$, indicating the number of lines.

The next $N$ lines each contain three integers $A_i, B_i, C_i$, meaning that line $i$ satisfies the equation.

Output Format

Output one integer: the number of triangles formed by these lines modulo $10^9+7$.

6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29 

10

5
-5 3 0
-5 -3 -30
0 1 0
3 7 35
1 -2 -1 

10

Hint

[Sample Explanation #1]

The figure above shows the positions of all lines in the Cartesian coordinate plane, and they form $10$ triangles in total.

[Constraints]

For $100\%$ of the testdata, $1 \le N \le 3 \times 10^5$, and $|A_i|, |B_i|, |C_i| \le 10^9$.

[Notes]

The scoring of this problem follows the original COCI setting, with a full score of $140$.

This problem is translated from COCI2013_2014 CONTEST #5 *T5 TROKUTI.

Translated by ChatGPT 5