问题描述

在 $xy$ 平面的一些点上有一些村庄。
高濑将修建护城河，以保护这些村庄免受内战军队和女巫等敌人的侵害。

给定一个由0和1组成的 $4 \times 4$ 矩阵 $A = (A_{i, j})$。
对于每一对整数 $(i, j)$ $(1 \leq i, j \leq 4)$，如果 $A_{i, j} = 1$，则表示坐标 $(i-0.5, j-0.5)$ 处有一个村庄。

护城河将是平面上的多边形。高濑将根据以下条件修建它。(也请参见样本输入/输出 1 中的注解。)

1. 没有自相交。
2. 所有村庄都包含在多边形的内部。
3. 每个顶点的 x 和 y 坐标是介于 0 和 4 之间的整数(包括边界)。
4. 每条边与 x 轴或 y 轴平行。
5. 每个内角是 90 度或 270 度。

请输出高濑可以修建护城河的方式数量。

约束条件

• $A_{i, j} \in \{0, 1\}$
• 至少有一对 $(i, j)$ 满足 $A_{i, j} = 1$。

输入

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

$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

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

示例输出 1

1272

如下图所示，有两种有效的修建护城河方式。

如下图所示，有四种无效的修建护城河方式。

以下是上述无效方式的原因。

• 第一种方式违反了条件：“没有自相交。”
• 第二种方式违反了条件：“所有村庄都包含在多边形的内部。”
• 第三种方式违反了条件：“每个顶点的 x 和 y 坐标是介于 0 和 4 之间的整数。” (某些顶点的坐标不是整数。)
• 第四种方式违反了条件：“每条边与 x 轴或 y 轴平行。”

示例输入 2

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

示例输出 2

1