5006 - [COCI 2013-2014 #5] TROKUTI

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

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

保证没有三线共点。

Input

第一行,一个整数 N,表示直线条数;

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

Output

一个整数,表示这些直线围出的三角形对 10^9+7 取模后的个数。

Examples

Input

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

Output

10

Input

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

Output

10

Hint

【样例一解释】

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

【数据范围】

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

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题