题目描述

由于最近预算缩减， Farmer John 决定缩小农场规模，奶牛放牧的场地变成了一个 $5 \times 5$ 平方米的方形场地！场地被划分成一个 $5 \times 5$ 的方格矩阵，每个方格边长为 $1$ 米， $(1, 1)$ 是左上角方格的坐标， $(5, 5)$ 是右下角方格的坐标，如下所示：

(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)

每一个方格中都有美味的草，除了其中 $K$ （ $0 \le K \le 22$ ）个土地贫瘠的方格，这些方格中没有草， $K$ 是偶数。奶牛 Bessie 从 $(1, 1)$ 出发， Mildred 从 $(5, 5)$ 出发，这两个格子永远都有草。

每过半小时， Bessie 和 Mildred 都将吃完他们所在格子上的草，然后各自移动到一个相邻的有草的格子上（东南西北方向）。她们想吃完所有格子中的草，并且最终停留在同一个格子。请求出有多少种吃草方式。 Bessie 和 Mildred 总会移动到有草的格子上，并且她们不会走到同一个格子直到只剩下一个有草的格子。

输入格式

第 $1$ 行：整数 $K$ 。

第 $2 \dots K + 1$ 行：每行包括没有草的格子坐标 $(i, j)$ 。

输出格式

第 $1$ 行： Bessie 和 Mildred 吃完牧场中的所有草并最终停留在同一个格子上的吃草方式种数。

4
3 2
3 3
3 4
3 1

1

一开始的牧场如下所示，其中 `.` 表示草地方格， `x` 表示没有草的方格， `b` 表示 Bessie 的起始位置， `m` 表示 Mildred 的起始位置：

b . . . .

. . . . .

x x x x .

. . . . .

. . . . m

只有一中可能的吃草方式，两头奶牛最终停留在 $(3, 5)$ ，如下所示：

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