Circuit Counting

Time limit2sMemory limit256 MB

Summary

Count the nonempty subsets of up to 40 given plane vectors whose sum is the zero vector.

Level: Medium6 of 10
Topics: Divide and conquer, Hash map
Solved: No attempts yet

Problem

You are given $N$ integer vectors $(x_i, y_i)$ in the plane. Start at the origin and treat each vector as a displacement from the previous position; the positions you visit form a path. For example, the vectors (1, 2), (2, 3), (-3, -5) form the path (0, 0), (1, 2), (3, 5), (0, 0). A path that ends at the origin is a circuit, so the path just described is a circuit.

You can form a path from any nonempty subset of the $N$ vectors, and whether the result is a circuit does not depend on the order in which the subset is used. Count the nonempty subsets that form circuits.

For example, take the vectors {(1, 2), (-1, -2), (1, 1), (-2, -3), (-1, -1)}. Exactly 4 of their subsets form circuits.

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

Input

The first line contains the number of vectors $N$ ( $1 \le N \le 40$ ).

Each of the next $N$ lines contains two integers $x$ and $y$ separated by a space, describing the vector $(x, y)$ ( $|x| \le 10$ , $|y| \le 10$ , $(x, y) \ne (0, 0)$ ).

All given vectors are distinct.

Output

Print the number of nonempty subsets of the given vectors that form circuits. The answer is guaranteed to be smaller than $10^{10}$ .

Examples6

Example 1
Input
```
5
1 2
1 1
-1 -2
-2 -3
-1 -1
```
Expected output
```
4
```
Example 2
Input
```
1
10 -10
```
Expected output
```
0
```
Example 3
Input
```
2
4 -7
-4 7
```
Expected output
```
1
```
Example 4
Input
```
2
1 0
0 1
```
Expected output
```
0
```
Example 5
Input
```
8
1 1
2 3
3 5
4 7
5 9
10 10
7 2
6 6
```
Expected output
```
0
```
Example 6
Input
```
3
3 4
-5 1
2 -5
```
Expected output
```
1
```