{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eSuppose you are given a sequence of $N$ integer-valued vectors in the plane $(x_i,y_i)$, $i\u003d1,\\dots,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 \u003cem\u003ecircuit\u003c/em\u003e. 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\u0027t depend on the ordering of the subset. How many nonempty subsets of the vectors form circuits?\u003c/p\u003e\n\u003cp\u003eFor 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$$\\left. \\begin{array}{l} \\{(1,2),(−1,−2)\\}\\\\ \\{(1,1),(−1,−1)\\}\\\\ \\{(1,2),(1,1),(−2,−3)\\}\\\\ \\{(1,2),(−1,−2),(1,1),(−1,−1)\\} \\end{array}\\right.$$\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eInput begins with an integer $N\\leq 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|\\leq 10$ and $(x,y)\\neq(0,0)$. Since the given vectors are a set, all vectors are unique.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eOutput the number of nonempty subsets of the given vectors that produce circuits. It\u0027s guaranteed that the answer is less than $10^{10}$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 2\n1 1\n-1 -2\n-2 -3\n-1 -1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}