#2684 Circuit Counting

1 s   128 MB  

Description

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

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

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

Sample Input

Sample Output

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

Source

ACM-ICPC North America Qualifier 2015 D