#9335. 「USACO12JAN」Grazing Patterns B 普及−

由于最近的预算削减，农夫约翰缩小了农场规模，使他的奶牛的牧场面积只有 米见方。

牧场区域可以看作一个 的方格矩阵，每个方格大小为 。

其中 是左上角方格的位置，而 是右下角方格的位置：

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

除了 个贫瘠的方格区域没有长草以外，其他方格内都充满了可口的青草。

奶牛贝茜从方格 开始吃草，奶牛米尔德瑞德从方格 开始吃草，这两个方格内一定有草。

每半个小时，两头奶牛就会吃光各自所在方格内的草，并移动到相邻（东、南、西、北）的有草的方格中。

她们想吃光牧场中所有的草，并最终到达完全相同的位置。

请计算发生这种情况的不同方式的数量。

两牛总是会移动到有草的方格内，除非是最后一个剩下的有草方格，否则她们永远都不会走到同一格子内。

第一行包含整数 。

接下来 行，每行包含两个整数 用来描述一个没有长草的方格的位置 。

输出两牛吃光所有草，并最终到达同一位置的所有可能方式的数量。

样例输入

4
3 2
3 3
3 4
3 1

样例输出

1

样例解释

初始时，牧场如下：

b  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  m

其中，x 为不长草的方格区域，b 为贝茜的开始区域，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

,
是偶数。