Suppose you are given a sequence of integer-valued vectors in the
plane ,
.
Beginning at the origin, we can generate a path by regarding
each vector as a displacement from the previous location. For
instance, the vectors , , form the path . 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 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 From these vectors we can construct 4 possible
subset circuits using
Input
Input begins with an integer on the first line. The next
lines each contain two
integer values and
forming the vector
, where
and
. 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 .
Sample Input 1 |
Sample Output 1 |
5
1 2
1 1
-1 -2
-2 -3
-1 -1
|
4
|