문제2684--Circuit Counting

### 2684: Circuit Counting

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 1  통과: 1
[제출] [채점기록] [묻고답하기]

#### 문제 설명

Suppose you are given a sequence of N integer-valued vectors in the plane (xi, yi), i = 1, . . . , N. Beginning at the origin, we can generate a path by regarding each vector as a displacement from the previous location. For instance, the vectors (1, 2), (2, 3), (−3, −5) form the path (0, 0),(1, 2),(3, 5),(0, 0). We define a path that ends at the origin as a circuit. The example just given is a circuit. We could form a path using any nonempty subset of the N vectors, while the result (circuit or not) doesn’t depend on the ordering of the subset. How many nonempty subsets of the vectors form circuits?

For instance, consider the vectors {(1, 2),(−1, −2),(1, 1),(−2, −3),(−1, −1)} From these vectors we can construct 4 possible subset circuits using

{(1, 2), (−1, −2)}
{(1, 1), (−1, −1)}
{(1, 2), (1, 1), (−2, −3)}
{(1, 2), (−1, −2), (1, 1), (−1, −1)}

#### 입력 설명

Input begins with an integer N ≤ 40 on the first line. The next N lines each contain two integer values x and y forming the vector (x, y), where |x|, |y| ≤ 10 and (x, y) 6= (0, 0). Since the given vectors are a set, all vectors are unique.

#### 출력 설명

Output the number of nonempty subsets of the given vectors that produce circuits. It’s guaranteed that the answer is less than 1010.

#### 입력 예시 Copy

5
1 2
1 1
-1 -2
-2 -3
-1 -1

#### 출력 예시 Copy

4