5006 - [COCI 2013-2014 #5] TROKUTI

给定 NN 条在平面直角坐标系内的直线，这些直线上的点满足 A_ix+B_iy+C_i=0。

请你求出这些直线围出的三角形个数，答案对 10^9+7 取模。

保证没有三线共点。

输入

第一行，一个整数 N，表示直线条数；

接下来 N 行，每行 3 个正整数 A_i,B_i,C_i ，表示直线 i 满足的条件。

输出

一个整数，表示这些直线围出的三角形对 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

提示

【样例一解释】

上图即为所有直线在平面直角坐标系上的位置，共围出了 10 个三角形。

【数据范围】

对于 100\% 的数据，1\le N\le 3\times 10^5。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题