Score : 500 points
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×4 matrix A=(Ai,j) consisting of 0 and 1.
For each pair of integers (i,j) (1≤i,j≤4) such that Ai,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.)
Print the number of ways in which Takahashi can construct the moat.
Input is given from Standard Input in the following format:
A1,1 A1,2 A1,3 A1,4 A2,1 A2,2 A2,3 A2,4 A3,1 A3,2 A3,3 A3,4 A4,1 A4,2 A4,3 A4,4
Print the number of ways in which Takahashi can construct the moat.
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
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.
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1