Do ngân sách bị cắt giảm gần đây, FJ đã thu hẹp trang trại đến mức khu vực chăn thả cho đàn bò chỉ còn là một cánh đồng hình vuông kích thước \(5\) mét nhân \(5\) mét! Cánh đồng được chia thành một lưới \(5 \times 5\) gồm các ô vuông kích thước \(1\) mét nhân \(1\) mét, trong đó \((1,1)\) là vị trí của ô trên cùng bên trái và \((5,5)\) là vị trí của ô dưới cùng bên phải:

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)

Mọi ô trong lưới đều có cỏ ngon, ngoại trừ \(K\) ô cằn cỗi (\(0 \le K \le 22\), \(K\) chẵn) không có cỏ. Bò Bessie bắt đầu gặm cỏ tại ô \((1,1)\), ô này luôn có cỏ; bò Mildred bắt đầu gặm cỏ tại ô \((5,5)\), ô này cũng luôn có cỏ.

Cứ mỗi nửa giờ, Bessie và Mildred ăn hết toàn bộ cỏ trong ô tương ứng của mình, rồi mỗi cô di chuyển đến một ô có cỏ kề cạnh (phía bắc, nam, đông hoặc tây). Họ muốn ăn hết tất cả các ô có cỏ và kết thúc tại chính xác cùng một vị trí cuối cùng. Hãy tính số cách khác nhau để điều này xảy ra. Bessie và Mildred luôn di chuyển vào các ô có cỏ, và họ không bao giờ cùng di chuyển vào một ô, trừ khi đó là ô có cỏ cuối cùng còn lại.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(K\).
• \(K\) dòng tiếp theo, mỗi dòng chứa vị trí \((i,j)\) của một ô không có cỏ dưới dạng hai số nguyên \(i\) và \(j\) cách nhau bởi dấu cách.

Dữ liệu ra

• Dòng đầu tiên chứa số cách khác nhau mà Bessie và Mildred có thể đi qua cánh đồng để ăn hết cỏ và kết thúc tại cùng một vị trí cuối cùng.

Ví dụ

4
3 2
3 3
3 4
3 1

1

b  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  m

b  b--b  b--b
|  |  |  |  |
b--b  b--b  b
            |
x  x  x  x b/m
            |
m--m--m--m--m
|
m--m--m--m--m

Nguồn

USACO 2012 January Contest, Bronze Division — Grazing Patterns

Tác giả đề: Brian Dean, 2012.