护城河

题目描述

在 $xy$ 平面上的一些点上分布着村庄。

高桥君打算修建护城河，以保护这些村庄免受军队、魔女等敌人的侵害。

给定一个由 $0$ 和 $1$ 组成的 $4 \times 4$ 矩阵 $A = (A_{i, j})$。

对于每对满足 $A_{i, j} = 1$ 的整数 $(i, j)$（$1 \le i, j \le 4$），在坐标 $(i-0.5, j-0.5)$ 处有一个村庄。

护城河是平面上的一个多边形。高桥君修建它时须满足以下条件（参见样例输入/输出 1 的说明）：

• 没有自交。
• 所有村庄都包含在多边形的内部。
• 每个顶点的 $x$ 坐标和 $y$ 坐标都是 $0$ 到 $4$（含）之间的整数。
• 每条边都平行于 $x$ 轴或 $y$ 轴。
• 每个内角为 $90$ 度或 $270$ 度。

输出高桥君可以修建护城河的方案数。

输入格式

输入按以下格式从标准输入给出：

$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ $A_{1, 4}$
$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ $A_{2, 4}$
$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ $A_{3, 4}$
$A_{4, 1}$ $A_{4, 2}$ $A_{4, 3}$ $A_{4, 4}$

输出格式

输出高桥君可以修建护城河的方案数。

样例

1 0 0 0
0 0 1 0
0 0 0 0
1 0 0 0

1272

下图中所示的修建护城河的两种方式是合法的。

下图中所示的修建护城河的四种方式是非法的。

这些方式非法的原因如下：

• 第一种方式违反了「没有自交」这一条件。
• 第二种方式违反了「所有村庄都包含在多边形的内部」这一条件。
• 第三种方式违反了「每个顶点的 $x$ 坐标和 $y$ 坐标都是 $0$ 到 $4$ 之间的整数」这一条件（有些顶点的坐标不是整数）。
• 第四种方式违反了「每条边都平行于 $x$ 轴或 $y$ 轴」这一条件。

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

1

数据范围

• $A_{i, j} \in \{0, 1\}$
• 至少存在一对 $(i, j)$ 使得 $A_{i, j} = 1$