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
统计
上一题 下一题