|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
C - Counting Self-Rotating Subsets
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
A set of points in the plane is self-rotating if there is a point $P$, the center, and an angle $\alpha$, expressed in degrees, where $0 < \alpha < 360$, such that the rotation of the plane, with center $P$ and angle $\alpha$, maps every point in the set to some point also in the set.
You are given a set of $N$ distinct points, all having integer coordinates. Find the number of distinct subsets of size $1, 2, \ldots, N$ that are self-rotating. Two subsets are considered distinct if one contains a point that the other does not contain.
Input
The first line of the input contains one integer $N$ representing the number of points in the input set ($1 \le N \le 1000$). Each of the following $N$ lines describes a different point of the set, and contains two integers $X$ and $Y$ giving its coordinates in a Cartesian coordinate system ($-10^9 \le X, Y \le 10^9$). All points in the input set are distinct.
Output
Output a single line containing $N$ integers $S_1, S_2, \ldots, S_N$. For $i=1,2,\ldots,N$ the integer $S_i$ must be the number of subsets of $i$ points of the input set that are self-rotating. Since these numbers can be very big, output them modulo $10^9 + 7$.
Sample test(s)
Input
3
1 1
2 2
1 0
Output
3 3 0
Input
7
-2 0
-1 1
0 2
0 0
2 0
1 -1
0 -2
Output
7 21 5 5 3 1 1
Input
1
-1000000000 1000000000
Output
1