407631: GYM102861 J Collecting Data

Acre and Amanda are very curious and are always looking for patterns around them. They routinely collect and analyze data from various sources (city traffic, rainfall, number of leaves that fall from trees), hoping to find interesting patterns.

Their last expedition produced a very promising data set: it followed a perfectly straight line! Formally, it was a list of $$$N/2$$$ pairs of integers, possibly repeated. When these pairs were plotted as points in the Cartesian plane, all of them were perfectly collinear! Pleased, Acre and Amanda stored this data as a table containing the pairs of integers.

Unfortunately, while Acre and Amanda were out collecting more data, their infant son entered their office and scrambled the data table, by shuffling all the values in it. Now, all Acre and Amanda have left are the $$$N$$$ shuffled integers. They want to try to reconstruct the original data table from them.

Formally, Acre and Amanda want to arrange these integers into $$$N/2$$$ pairs, where each pair represents a point in the Cartesian plane, in such a way that all these points are collinear. The given list of integers can have repeated values, and each value must be used exactly as many times as it appears in the list. The resulting data set can also have repeated data points.

Since there may be several different suitable datasets that can be formed with the given integers, Acre and Amanda want to know the number of such datasets. Two datasets are considered different if and only if there is a point that appears more times in one data set than in the other.

The first line contains a single integer $$$N$$$, the length of the given list of integers. $$$N$$$ is always even, because it is twice the amount of points from the original data set. The second line contains $$$N$$$ integers, representing the list of values from the shuffled data table.

The integers are separated by a single space.

$$$4 \le N \le 200$$$.

Each value $$$I$$$ from the list is in the interval $$$−10000 \le I \le 10000$$$.

The output must consist of a single line with a single integer, the number of different ways the list of integers can be arranged into collinear points. Since this number can be very large, print the answer mod $$$1000000007$$$ $$$(10^9 + 7)$$$.

The answer can be zero for some cases.

8
1 2 3 5 20 18 16 12

2

6
1 2 3 4 5 20

0

8
1 2 5 5 5 5 8 9

10