Santa Claus and Rudolph

Time limit12sMemory limit128 MB

Summary

Count the closed tours that start and end at the single church, visiting every house once, where each move is a straight horizontal or vertical glide that may not pass over an already visited house.

Level: Medium7 of 10
Topics: Backtracking, DFS, Implementation, Matrix
Solved: No attempts yet

Problem

Santa Claus wants to give a present to every child in a certain neighborhood. Every house in the neighborhood has a child, so Santa must visit every house and deliver a present. This year Rudolph, who carries Santa, has a poor sense of direction and cannot land anywhere except on a building. So Santa wants to plan out how to deliver the presents in advance.

The neighborhood is divided into 1×1 cells, and each cell is a house, a church, or empty land. There is exactly one church. Santa and Rudolph start at the church, deliver a present to every house, and must return to the church. They must obey the following rules.

Rudolph can fly only in straight lines in the four directions (north, south, east, west), and cannot change direction while in the air.
Santa may freely fly over a house that has not yet received a present. If he lands on such a house he must deliver a present there, and then he takes off again in one of the four directions.
Every house has a fireplace, unlit until Santa arrives. To avoid delivering a present to the same house twice, Santa lights the fireplace as he takes off. Once it is lit, smoke rises from the chimney, so he cannot fly over a house that has already received a present.
Santa may freely fly over the church. However, a service is in progress, so he cannot land at the church until every house has received a present.
Santa may freely fly over empty land, but he cannot land on empty land.

Given the layout of the neighborhood, write a program that finds the number of ways Santa and Rudolph can deliver the presents.

Input

The first line contains the width $m$ and the height $n$ of the neighborhood, separated by a space. ( $1 \le m, n \le 10$ ) Each of the next $n$ lines contains $m$ numbers separated by spaces. Each number describes the state of that cell and is one of 0, 1, 2: 0 is empty land, 1 is a house, and 2 is the church. There is always exactly one church, and the number of houses is between 1 and 23, inclusive.

Output

Print the number of ways the presents can be delivered. This value is guaranteed to be at most 2,000,000.

Examples2

Example 1
Input
```
3 2
1 0 1
1 0 2
```
Expected output
```
2
```
Example 2
Input
```
3 3
1 1 1
1 0 1
1 1 2
```
Expected output
```
6
```