题目描述

预算吃紧，FJ 把放牧区压缩成一块 5×5 的方格田。
网格坐标 (i,j) 中，1 ≤ i,j ≤ 5，(1,1) 左上角，(5,5) 右下角。
除 K 块贫瘠方格（无草）外，其余 25-K 块方格都长满草。

• 贝西 从 (1,1) 开始吃草；
• 米尔德里德 从 (5,5) 开始吃草。

每 半分钟：

• 两人同时吃完当前方格的所有草；
• 然后各自移动到 相邻 的草地方格（上下左右，不斜走）；
• 两人不会同时进入同一方格，除非那是最后一块草。

目标：两人走遍 所有草地方格，最终停在 同一个终点。
求满足条件的路径方案数。

输入格式

• 第 1 行：整数 $K\ (0\le K\le 22,\ K\ \text{为偶数})$。
• 第 $2\sim K+1$ 行：每行两个空格分隔的整数 $i\ j$，表示贫瘠方格坐标。

输出格式

• 第 1 行：一个整数，表示合法路径方案数。

样例

样例输入

4
3 2
3 3
3 4
3 1

样例输出

1

样例解释

贫瘠方格为 (3,2) (3,3) (3,4) (3,1)。
唯一合法方案：两人最终都停在 (3,5)。

数据范围与提示

• 网格固定 5×5。
• 起点 (1,1) 与 (5,5) 一定长草。