상근이네 집 근처에는 군사 기지가 있다. 군사 기지에는 참호가 많이 있으며, 참호는 평면 위의 선분으로 모델링 할 수 있다.

매일 밤 대부분의 군인들은 잠을 자고, 군인 세 명은 밤새도록 참호를 감시한다. 두 군인이 서로 볼 수 있으려면, 그들 연결하는 선분이 모두 참호안에 있어야 하며, 다른 군인은 그 사이에 없어야 한다.

보안 상의 이유 때문에 군인은 모두 서로를 볼 수 있어야 한다. 군인을 배치할 수 있는 방법의 수는 총 몇 가지가 있을까?

입력 형식

첫째 줄에 참호의 수 N이 주어진다. (1 ≤ N ≤ 20) 다음 N개 줄에는 참호의 정보가 네 양의 정수 X1, Y1, X2, Y2로 주어진다. 좌표는 모두 1000보다 작거나 같은 양의 정수 또는 0이다. (X1, Y1)과 (X2, Y2)는 참호의 양 끝 점이다.

참호는 겹칠 수도 있으며, 끝 점을 공유할 수도 있다.

출력 형식

첫째 줄에 군인을 배치하는 방법의 수를 출력한다.

예제 입력 1

6
0 0 1 0
0 0 0 1
1 0 1 1
0 1 1 1
0 0 1 1
1 0 0 1

예제 출력 1

8

예제 입력 2

4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4

예제 출력 2

1

예제 입력 3

3
2 2 3 2
3 2 3 3
3 3 2 3

예제 출력 3

0