기하 조합론

Grace는 기하 조합론이라는 새로운 이론을 연구하고 있다. 이 이론은 조합적 대상의 기하학적 성질을 다루는 학문이다.

평면 위의 두 삼각형을 생각하자. 하나는 파스칼의 삼각형이고, 다른 하나는 일반 삼각형이다. 파스칼의 삼각형은 원점 $(0, 0)$에 꼭짓점이 있고, 두 변은 상반평면 각 사분면의 대각선을 따라 놓여 있다. 정확히는 점 $(i, i)$와 $(-i, i)$에 1이 적혀 있다. 그 사이의 점 $(-i+2k, i)$에는 점 $(-i+2k+1, i-1)$과 $(-i+2k-1, i-1)$에 적힌 수의 합이 적혀 있다. 이때 $k$는 1부터 $i-1$까지의 모든 값이다.

일반 삼각형은 꼭짓점이 $(x_A, y_A)$, $(x_B, y_B)$, $(x_C, y_C)$이다.

교차값은 파스칼의 삼각형에 적힌 값 중 일반 삼각형의 내부 또는 경계 위에 있는 값들의 합이다. 이 교차값을 계산하는 프로그램을 작성하시오.

첫 번째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 5$)가 주어진다. 이어지는 $t$개의 줄에는 각각 정수 여섯 개 $x_A, y_A, x_B, y_B, x_C, y_C$ ($-10^6 \le x_A, y_A, x_B, y_B, x_C, y_C \le 10^6$)가 주어진다. 각 테스트 케이스에서 세 점은 한 직선 위에 있지 않다.

각 테스트 케이스마다 교차값을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.