Problem Description

Santa Claus has arrived in JOI Town from the sky once again. Every house in JOI Town has children, so Santa Claus must deliver presents to all the houses. However, this year's reindeer is somewhat direction-challenged and can only land on buildings, so Santa Claus must devise a route to deliver all the presents.

JOI Town is divided into blocks oriented north-south and east-west, and each block is either a house, a church, or an empty lot. There is exactly one church in JOI Town. Following these rules, Santa Claus and the reindeer start from the church, deliver presents to all houses once, and then return to the church:

• The reindeer is direction-challenged this year and can only fly straight in one of the four cardinal directions and cannot change direction in mid-air.
• The reindeer can freely pass over houses that haven't received a present yet. It can land on houses that haven't received a present, and when it lands, it must deliver a present, then take off in one of the four cardinal directions.
• In JOI Town, houses keep their chimneys off until Santa Claus arrives on Christmas night. After Santa Claus leaves, they light their chimneys, and smoke comes out. Therefore, the reindeer cannot pass over houses that have already received a present.
• The reindeer can freely pass over the church. However, since a service is being held at the church, they cannot land there until all presents have been delivered.
• The reindeer can freely pass over empty lots but cannot land on them.

Given the structure of the town as input, create a program to determine how many different routes Santa Claus and the reindeer can take to deliver all the presents.

Input Format

The input consists of $ n + 1 $ lines. The first line contains two integers $ m $ ($1 \leq m \leq 10$) and $ n $ ($1 \leq n \leq 10$) separated by a space. From the second line to the $ n + 1 $ line, each line contains $ m $ values separated by spaces, which are either $ 0 $, $ 1 $, or $ 2 $, representing the state of each block. If we denote the block at the $ i $-th from the north and $ j $-th from the west as $ (i, j) $ ($1 \leq i \leq n$, $1 \leq j \leq m$), the $ j $-th value on the $ i + 1 $-th line represents:
- $ 0 $ if the block $ (i, j) $ is an empty lot,
- $ 1 $ if the block $ (i, j) $ is a house,
- $ 2 $ if the block $ (i, j) $ is a church.

There is exactly one church, and the number of houses is between $ 1 $ and $ 23 $ inclusive. For the grading input data, the number of routes does not exceed $ 2,000,000 $.

Output Format

The output consists of one line containing a single integer representing the number of different routes to deliver all the presents.

Sample Input and Output

Sample Input #1

3 2
1 0 1
1 0 2

Sample Output #1

2

Sample Input #2

3 3
1 1 1
1 0 1
1 1 2

Sample Output #2

6

Notes/Hints

Sample Explanation 1

- - - - - -

Sample Explanation 2

All 6 routes for Sample Input #2 (the numbers indicate the order of delivery)

见题面 Input 部分

见题面 Output 部分