Cutting the Stone Slab

A stone slab is given as an N x N grid. Each cell is empty, contains an impurity, or contains a crystal. You want to cut the slab into pieces so that every final piece satisfies both conditions below.

• The piece contains no impurity.
• The piece contains exactly one crystal.

To remove an impurity, a cut must be a straight line passing through a cell that contains an impurity. Because of the grain of the slab, each cut must be horizontal or vertical. The first cut may use either direction, but when a resulting piece is cut again, the new cut cannot have the same direction as the cut that created that piece.

A cut line must pass all the way across the current piece and split it into two pieces. A line containing a crystal cannot be cut. Count all possible cutting processes.

The first line contains the size N of the slab. 1 <= N <= 20.

Each of the next N lines contains N integers describing one row of the slab, separated by spaces.

• 0: empty cell
• 1: impurity
• 2: crystal

The number of crystals is at most 15.

Print the number of ways to cut the slab so that every final piece contains no impurity and exactly one crystal.

If there is no possible way, print -1.