Problem: problem

Santa Claus came from the sky to JOI town this year as well. Since every house in JOI has children, this Santa Claus must give out presents to every house in JOI. However, this year the reindeer I am carrying is a little deaf and I can only get off the top of the building, so it seems that I have to devise a little route to distribute gifts to all the houses.

JOI Town is divided into north, south, east and west, and each section is a house, a church, or a vacant lot. There is only one church in JOI town. According to the following rules, Santa Claus and reindeer depart from the church, give out one gift to every house, and then return to the church.

* This year's reindeer is a little deaf, so it can only fly straight in either the north, south, east, or west, and cannot change direction in the air.
* You can pass freely over the house where you haven't handed out the presents yet. You can get off at a house that hasn't given out presents yet. Whenever I get home, I give out presents and then take off in either direction of north, south, east or west.
* At the house in JOI town, I spend Christmas night without the fireplace until Santa Claus arrives, but after Santa Claus takes off, I turn on the fireplace. When you turn on the fireplace, smoke comes out of the chimney, so you can't pass over the house where you've finished giving out presents.
* You can pass freely over the church. However, since worship is held in the church, you cannot go down to the church until you have distributed all the presents.
* You can pass freely over the vacant lot, but you cannot get off at the vacant lot.


Create a program that asks how many directions Santa Claus and reindeer can give gifts to, given the structure of the town as input.

input

The input consists of multiple datasets. Each dataset is given in the following format.

Each dataset has n + 1 rows. On the first line, the integer m (1 ≤ m ≤ 10) and the integer n (1 ≤ n ≤ 10) are written separated by a space. In each line from the 2nd line to the n + 1th line, m of 0, 1, or 2 are written, separated by a blank, and each represents the state of each section. If we write the i-th section from the north and the j-th section from the west as (i, j) (1 ≤ i ≤ n, 1 ≤ j ≤ m), the j-th value on the i + 1 line is If the lot (i, j) is a vacant lot, it will be 0, if it is a house, it will be 1, and if it is a church, it will be 2. The number of churches is 1, and the number of houses is 1 or more and 23 or less. However, in the input data for scoring, the number of directions to be distributed does not exceed 2000000.

When both m and n are 0, it indicates the end of input. The number of data sets does not exceed 5.

Input / output example

Input example


3 2
1 0 1
1 0 2
3 3
1 1 1
1 0 1
1 1 2
0 0


Output example


2
6


<image>


Figure: All 6 directions to the second input example (numbers indicate the order of distribution)

The above question sentences and the data used for the automatic referee are the question sentences created and published by the Japan Committee for Information Olympics and the test data for scoring.



output

For each dataset, an integer indicating how many directions to distribute gifts is output on one line.

Example

Input

3 2
1 0 1
1 0 2
3 3
1 1 1
1 0 1
1 1 2
0 0


Output

2
6

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using Int = signed;

Int s[20][20],idx[20][20],cnt,pru;
Int u[40][4];
Int num[40],ok[40];
vector<vector<vector<Int> > > G;

unordered_map<int, int> dp;
Int dfs(Int z,Int b){
  if(b==0) dp.clear();
  int hs=(b<<5)|z;
  if((z&3)==0) if(dp.count(hs)) return dp[hs];

  Int res=0;
  
  for(Int k=0;k<4;k++){
    for(auto w:G[z][k]){
      if((b>>w)&1) break;
      Int nb=b^(1<<w),flg=1;
      for(Int i=0;i<4;i++){
	if(u[w][i]>=cnt) continue; 
	num[u[w][i]]--;
	if((~nb>>u[w][i])&1)
	  flg&=num[u[w][i]]>=1;
      }
      if(flg){
	if(nb+1==(1<<cnt)) res+=ok[w];
	else if((nb&pru)!=pru) res+=dfs(w,nb);
      }
      for(Int i=0;i<4;i++) num[u[w][i]]++;
    }
  }
  
  if((z&3)==0) dp[hs]=res;
  return res;
};

//INSERT ABOVE HERE
signed main(){
  Int w,h;
  while(cin>>w>>h,w+h){
    for(Int i=0;i<h;i++)
      for(Int j=0;j<w;j++)
	cin>>s[i][j];
    
    cnt=0;
    for(Int i=0;i<h;i++){
      for(Int j=0;j<w;j++){
	idx[i][j]=cnt;
	cnt+=s[i][j]==1;
      }
    }
    
    for(Int i=0;i<h;i++)
      for(Int j=0;j<w;j++)
	if(s[i][j]==2) idx[i][j]=cnt;
    
    Int dy[]={0,0,1,-1};
    Int dx[]={1,-1,0,0};
    auto in=[&](Int y,Int x){return 0<=y&&y<h&&0<=x&&x<w;};    

    G.clear();
    G.resize(cnt+1);
    
    memset(num,0,sizeof(num));    
    memset(ok,0,sizeof(ok));
    
    for(Int y=0;y<h;y++){
      for(Int x=0;x<w;x++){
	if(s[y][x]==0) continue;
	Int z=idx[y][x];
	G[z].resize(4);
	for(Int k=0;k<4;k++){
	  Int ny=y,nx=x;
	  while(1){
	    ny+=dy[k],nx+=dx[k];
	    while(in(ny,nx)&&s[ny][nx]==0)
	      ny+=dy[k],nx+=dx[k];
	    if(!in(ny,nx)) break;	    
	    if(s[ny][nx]==2) ok[z]=1;
	    else G[z][k].emplace_back(idx[ny][nx]);
	  }
	}
	
	for(Int k=0;k<4;k++){
	  u[z][k]=cnt+1;
	  for(auto w:G[z][k]){
	    u[z][k]=w;
	    num[w]++;
	    break;
	  }
	}
	
	if(z==cnt){
	  pru=0;
	  for(Int k=0;k<4;k++){
	    for(auto w:G[z][k]){
	      pru|=(1<<w);
	      break;
	    }
	  }
	}
      }
    }

    cout<<dfs(cnt,0)<<endl;
  }
  return 0;
}