Contest Duration: - (local time) (100 minutes) Back to Home
E - Moat /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

xy -平面上のいくつかの点に村があります。

01 からなる 4 \times 4 行列 A = (A_{i, j}) が与えられます。
A_{i, j} = 1 を満たす整数の組 (i, j) (1 \leq i, j \leq 4) ごとに、座標 (i-0.5, j-0.5) に村があります。

お堀は平面上の多角形です。 高橋君は以下の条件をすべて満たすお堀を建設します（入力例１・出力例１の説明も参考にして下さい）。

1. 自己交差がない
2. 内部にすべての村を含む
3. すべての頂点の x 座標と y 座標は 0 以上 4 以下の整数
4. すべての辺は x 軸と y 軸のどちらかに平行
5. それぞれの内角の大きさは 90 度または 270

### 制約

• A_{i, j} \in \lbrace 0, 1\rbrace
• A_{i, j} = 1 となる (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


• 1 つ目の画像の例は、「自己交差がない」という条件を満たしません。
• 2 つ目の画像の例は、「内部にすべての村を含む」という条件を満たしません。
• 3 つ目の画像の例は、「すべての頂点の x 座標と y 座標は 0 以上 4 以下の整数」という条件を満たしません。（座標が整数でない頂点があります。）
• 4 つ目の画像の例は、「すべての辺は x 軸と y 軸のどちらかに平行」という条件を満たしません。

### 入力例 2

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


### 出力例 2

1


Score : 500 points

### Problem Statement

There are villages at some number of points in the xy-plane.
Takahashi will construct a moat to protect these villages from enemies such as civil armies and witches.

You are given a 4 \times 4 matrix A = (A_{i, j}) consisting of 0 and 1.
For each pair of integers (i, j) (1 \leq i, j \leq 4) such that A_{i, j} = 1, there is a village at the coordinates (i-0.5, j-0.5).

The moat will be a polygon in the plane. Takahashi will construct it so that the following conditions will be satisfied. (See also the annotation at Sample Input/Output 1.)

1. There is no self-intersection.
2. All villages are contained in the interior of the polygon.
3. The x- and y-coordinates of every vertex are integers between 0 and 4 (inclusive).
4. Every edge is parallel to the x- or y-axis.
5. Every inner angle is 90 or 270 degrees.

Print the number of ways in which Takahashi can construct the moat.

### Constraints

• A_{i, j} \in \lbrace 0, 1\rbrace
• There is at least one pair (i, j) such that A_{i, j} = 1.

### Input

Input is given from Standard Input in the following format:

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}


### Output

Print the number of ways in which Takahashi can construct the moat.

### Sample Input 1

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


### Sample Output 1

1272


The two ways to construct the moat shown in the images below are valid.

The four ways to construct the moat shown in the images below are invalid.

Here are the reasons the above ways are invalid.

• The first way violates the condition: "There is no self-intersection."
• The second way violates the condition: "All villages are contained in the interior of the polygon."
• The third way violates the condition: "The x- and y-coordinates of every vertex are integers between 0 and 4." (Some vertices have non-integer coordinates.)
• The fourth way violates the condition: "Every edge is parallel to the x- or y-axis."

### Sample Input 2

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


### Sample Output 2

1