Mỗi ngày, Farmer John đi quanh trang trại để kiểm tra sức khỏe và tình trạng của \(N\) con bò (\(1 \leq N \leq 10\)).

Vị trí của mỗi con bò được mô tả bằng một điểm trên mặt phẳng hai chiều, còn Farmer John xuất phát tại gốc tọa độ \((0,0)\). Để hành trình thú vị hơn, Farmer John quyết định chỉ đi theo các hướng song song với các trục tọa độ, tức là chỉ đi về phía bắc, nam, đông hoặc tây. Hơn nữa, ông chỉ đổi hướng di chuyển khi đến vị trí của một con bò (nếu muốn, ông cũng có thể đi qua vị trí của một con bò mà không đổi hướng). Khi đổi hướng di chuyển, ông có thể rẽ \(90\) độ hoặc quay \(180\) độ. Sau khi thăm tất cả đàn bò, hành trình của FJ phải đưa ông trở về gốc tọa độ.

Hãy tính số hành trình khác nhau mà FJ có thể thực hiện để thăm \(N\) con bò nếu ông đổi hướng đúng một lần tại vị trí của mỗi con. Ông được phép đi qua vị trí của một con bò mà không đổi hướng bao nhiêu lần tùy ý. Cùng một lộ trình hình học nhưng đi theo chiều xuôi và chiều ngược được tính là hai hành trình khác nhau.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa tọa độ \(x\) và \(y\), cách nhau bởi dấu cách, của điểm thứ \(i\) (mỗi giá trị nằm trong khoảng \(-1000 \ldots 1000\)).

Dữ liệu ra

In ra số hành trình khác nhau mà FJ có thể thực hiện. Kết quả có thể bằng 0 nếu không có hành trình hợp lệ.

Ví dụ

4
0 1
2 1
2 0
2 -5

2

Nguồn

USACO 2012 March Contest, Bronze Division — Connect the Cows. Tác giả đề: Brian Dean (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=122