직선으로 만드는 삼각형

면접 대비

시간 제한1초메모리 제한128 MB

요약
주어진 직선 중 삼각형을 이루는 세 직선 조합 수를 평행한 직선을 제외하고 셉니다.
난이도

보통10점 중 4점

유형
해시맵, 조합론, 수학
정답자
아직 제출이 없습니다

문제

상근이는 좌표평면 위에 Aix+Biy+Ci=0A_i x + B_i y + C_i = 0 꼴로 나타낼 수 있는 직선 NN개를 가지고 있다.

상근이가 가진 직선 중 세 개를 골라 만들 수 있는 삼각형의 개수를 구하는 프로그램을 작성하시오.

세 직선이 한 점에서 만나는 경우는 없다.

입력

첫째 줄에 직선의 개수 NN이 주어진다. (1≤N≤300,0001 \le N \le 300{,}000)

둘째 줄부터 NN개 줄에 ii번째 직선의 AiA_i, BiB_i, CiC_i가 순서대로 주어진다. 모든 수는 절댓값이 10910^9 이하인 정수이고, AiA_i와 BiB_i가 동시에 0인 직선은 없다.

출력

첫째 줄에 주어진 직선으로 만들 수 있는 삼각형의 개수를 출력한다. 개수가 매우 많을 수 있으므로, 1,000,000,007로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

    입력
    6
    0 1 0
    -5 3 0
    -5 -2 25
    0 1 -3
    0 1 -2
    -4 -5 29
    
    예상 출력
    10
    
  2. 예제 2

    입력
    5
    -5 3 0
    -5 -3 -30
    0 1 0
    3 7 35
    1 -2 -1
    
    예상 출력
    10