Cho \(N\) đường thẳng có dạng \(Ax+By+C=0\) trên mặt phẳng tọa độ. Biết rằng không có ba đường thẳng nào cùng giao nhau ở 1 điểm. Bạn hãy tính số lượng tam giác tạo thành từ các đường thẳng. Vì kết quả có thể rất lớn, đáp số cuối cùng sẽ modulo \(10^9+7\).

Input

• Dòng đầu tiên là số nguyên dương \(N\), là số lượng đường thẳng. \((1 \leq N \leq 3 \times10^5)\)
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(A, B, C\) (Các giá trị tuyệt đối không vượt quá \(10^9\))

Output

• Một dòng duy nhất là số lượng tam giác tạo thành.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 5000\)
• Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm

Example

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

10