Heating Main

A heating main must connect the top side of the top-left cell $(1, 1)$ to the right side of the bottom-right cell $(n, m)$ inside a rectangular area of $n$ columns and $m$ rows. The main is assembled from pipe segments, and each cell holds at most one pipe, which joins exactly two of that cell's four sides.

Only four pipe types are available, and they may not be rotated:

• Pipe 1 joins the top and right sides.
• Pipe 2 joins the bottom and left sides.
• Pipe 3 joins the left and right sides.
• Pipe 4 joins the top and bottom sides.

In particular, no pipe joins the top side to the left side, and no pipe joins the right side to the bottom side.

Two pipes in neighbouring cells are connected only when both have an end on the wall they share: if two adjacent cells both belong to the main, their pipe ends must meet on the common side. The whole main must stay inside the area — no pipe may stick out of it.

At the start, every cell is one of the following:

• empty — a new pipe of any of the four types may be built here;
• an already-built pipe (type 1-4) — it may be reused as a link in the main but cannot be replaced by a different pipe, and the main may also leave it unused;
• a garden — the main may not use this cell.

For the area in Pic. 2, the main can be built in exactly three ways, shown in Pic. 3.

Write a program that counts how many different heating mains can be built.

The first line contains two integers $n$ and $m$ ($1 \le n \le 10$, $1 \le m \le 10$), separated by a space: the number of columns and the number of rows.

Each of the next $m$ lines contains $n$ integers separated by spaces. The $j$-th integer on the $i$-th of these lines describes the cell in row $i$, column $j$:

• $0$ — an empty cell;
• $1$–$4$ — an already-built pipe of the matching type from Pic. 1;
• $5$ — a garden.

Print a single integer: the number of different heating mains that can be built.