시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 6 5 62.500%

문제

A set of points in the plane is self-rotating if there is a point P, the center, and an angle α, expressed in degrees, where 0 < α < 360, such that the rotation of the plane, with center P and angle α, 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, . . . , N that are self-rotating. Two subsets are considered distinct if one contains a point that the other does not contain.

입력

The first line of the input contains one integer N representing the number of points in the input set (1 ≤ N ≤ 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 (−109 ≤ X, Y ≤ 109 ). All points in the input set are distinct.

출력

Output a single line containing N integers S1, S2, . . . , SN . For i = 1, 2, . . . , N the integer Si 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 109 + 7.

예제 입력 1

3
1 1
2 2
1 0

예제 출력 1

3 3 0

예제 입력 2

7
-2 0
-1 1
0 2
0 0
2 0
1 -1
0 -2

예제 출력 2

7 21 5 5 3 1 1

예제 입력 3

1
-1000000000 1000000000

예제 출력 3

1

힌트