데이터 짝짓기

Acre와 Amanda는 호기심이 매우 많아서 주변에서 항상 패턴을 찾는다. 두 사람은 도시 교통량, 강우량, 나무에서 떨어지는 잎의 수처럼 여러 출처에서 데이터를 정기적으로 모으고 분석하며 흥미로운 패턴을 찾으려 한다.

지난 탐사에서 두 사람은 완벽한 일직선을 이루는 데이터를 얻었다. 형식적으로는 같은 값이 반복될 수도 있는 정수 쌍 N/2개의 목록이다. 이 쌍들을 직교 좌표평면의 점으로 나타내면 모든 점이 정확히 한 직선 위에 있었다. 두 사람은 이 데이터를 정수 쌍으로 이루어진 표로 저장했다.

그런데 두 사람이 데이터를 더 모으러 나간 사이, 어린 아들이 사무실에 들어와 표의 값들을 서로 바꿔 놓아 표를 엉망으로 만들었다. 이제 두 사람에게 남은 것은 표에 있던 N개의 값을 섞은 것뿐이다. 두 사람은 이 값들로 원래 표를 복원하려 한다.

형식적으로, 두 사람은 이 수들을 N/2개의 쌍으로 묶어 각 쌍이 평면의 한 점이 되도록 하고, 모든 점이 한 직선 위에 있도록 하려 한다. 목록에는 같은 값이 여러 번 있을 수 있으며, 각 값은 목록에 나타난 횟수만큼 정확히 사용해야 한다. 만들어지는 데이터에는 같은 점이 반복해서 들어갈 수 있다.

두 사람은 주어진 목록으로 서로 다른 데이터 집합을 몇 개나 만들 수 있는지 알고 싶어 한다. 여러 개가 나올 수 있기 때문이다. 두 데이터 집합은 어떤 점이 한쪽에서 다른 쪽보다 더 많이 나타날 때에만 서로 다르다.

첫 줄에는 주어진 목록의 크기 N이 하나의 정수로 주어진다. N은 원래 데이터 점 개수의 두 배이므로 항상 짝수이다. 둘째 줄에는 섞인 표의 값 N개가 주어진다.

정수들은 공백 한 칸으로 구분된다.

정수 목록을 같은 직선 위의 점을 나타내는 쌍으로 나누는 서로 다른 방법의 수를 한 줄에 출력한다. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

경우에 따라 답은 0일 수 있다.

$4 \le N \le 200$

목록의 각 정수 $I$는 $-10000 \le I \le 10000$을 만족한다.