Triangle Counting by Lines

Given N lines in the Cartesian coordinate system. The equation of the i-th line is given by \(A_i x + B_i y + C_i = 0\). It is guaranteed that no three lines are concurrent.

A triangle is formed by three lines if and only if every pair of lines among them is non‐parallel. Two lines \(A_i x+B_i y+C_i=0\) and \(A_j x+B_j y+C_j=0\) are parallel if \(A_iB_j - A_jB_i = 0\).

Output the number of triangles formed by these lines, taken modulo \(10^9+7\).

Hint: If you group lines by their direction (slope), then a triangle is formed by choosing one line from each of three distinct groups. If the counts in each group are \(n_1, n_2, \dots, n_k\), then the answer is given by \(\sum_{1 \le i < j < k \le K} n_i n_j n_k\). This can also be computed via the formula:

\[ \text{Answer} = \frac{\left(\sum_{i=1}^k n_i\right)^3 - 3\left(\sum_{i=1}^k n_i\right)\left(\sum_{i=1}^k n_i^2\right) + 2\left(\sum_{i=1}^k n_i^3\right)}{6} \pmod{10^9+7}. \]

inputFormat

The first line contains a single integer N (3 \(\leq N \leq 10^5\)) denoting the number of lines.

Each of the following N lines contains three integers \(A_i\), \(B_i\), \(C_i\) (\(|A_i|,|B_i|,|C_i| \leq 10^9\)) representing the coefficients of the i-th line.

outputFormat

Output a single integer, the number of triangles enclosed by the given lines, modulo \(10^9+7\).

sample

3
1 0 0
0 1 0
1 1 -1

1