Điểm: 400 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input
6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29 
Output
10
Note


Bình luận