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 <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define DEB 0

const int dx[] = {1,0,-1,0}; //r,d,l,u
const int dy[] = {0,1,0,-1};

int w,h,sx,sy,home,last;
int field[16][16];
int num[16][16];
int kari[32];
vector<pair<int,int> > v;

#if DEB
stack<int> st;
#endif

class state{
public:
  char x,y;
  int s;
  state(char _x, char _y, int _s){
    x = _x;
    y = _y;
    s = _s;
  }
  
  bool operator<(const state& a)const{
    if( s==a.s ){
      if( x==a.x ) return y<a.y;
      else         return x<a.x;
    }else{
      return s<a.s;
    }
  }
  
};

map<state,int> msi;

inline int numofbits(int bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

inline bool isnotgoal(int s){
  return (((last&s)) == last);
}
inline int isnot(int s){
  rep(i,home)if( !(s&(1<<i)) ){
    if( (kari[i]&s)==kari[i] ) return i;
  }
  return -1;
}
inline bool inside(int x, int y){
  return (x<0 || y<0 || x>=w || y>=h);
}


int dfs(int x, int y, int s){
  if( (1<<home)-1 == s ){ //âÎÉßêé
    return 1;
  }
  if( isnotgoal(s) ){ //³ïÉßé½ßÌÆðÁïµ½©Ç¤©
    return 0;
  }
  if( msi.count(state(x,y,s)) ){ //ùÉÊÁ½óÔ
    return msi[state(x,y,s)];
  }
  
  int mask = (1<<home)-1;
  // v[gªu¯È¢ÆÌL³
  if( s>0 && numofbits(~s&mask)>1 && isnot(s&~(1<<num[y][x]))!=-1 ){
#if DEB
    printf("s:%d ,(%d,%d)  __%d  ___isnot:%d\n",s,x,y,s&~num[y][x],isnot(s&~num[y][x]));
    stack<int> tmp = st;
    while( !tmp.empty() ){
      printf("%d,",tmp.top());
      tmp.pop();
    }
    puts("\n");
#endif
    return 0;
  }
  
  int ret = 0;
  rep(k,4){
    for(int i=1; i<20; i++){
      int tx = x + dx[k]*i;
      int ty = y + dy[k]*i;
      if( inside(tx,ty) ) break;
      if( field[ty][tx]==1 ){
	field[ty][tx] = 0;
#if DEB
	st.push(num[ty][tx]);
#endif
	ret += dfs(tx,ty,s|(1<<num[ty][tx]));
	field[ty][tx] = 1;

#if DEB
	st.pop();
#endif

	break;
      }
    }
  }
  msi[state(x,y,s)] = ret;
  return ret;
}

int main(){

  while(scanf("%d%d",&w,&h),w|h){
    msi.clear();
    v.clear();
    memset(num,-1,sizeof(num));
    memset(kari,0,sizeof(kari));
    home = last = 0;
    rep(i,h){
      rep(j,w){
	scanf("%d",&field[i][j]);
	if( field[i][j]==2 ){
	  sx = j;
	  sy = i;
	}
	if( field[i][j]==1 ){
	  num[i][j] = home;
	  home++;
	  v.pb(mp(j,i));
	}
      }
    }

    // other homes
    rep(i,v.size()){
      rep(k,4){
	for(int j=1; j<20; j++){
	  int tx = v[i].first + dx[k]*j;
	  int ty = v[i].second + dy[k]*j;
	  if( inside(tx,ty) ) break;
	  if( field[ty][tx]==1 ){
	    kari[i] |= (1<<num[ty][tx]);
	  }
	}
      }
    }

    //last homes
    rep(k,4){
      for(int i=1; i<20; i++){
	int tx = sx + dx[k]*i;
	int ty = sy + dy[k]*i;
	if( inside(tx,ty) )break;
	if( field[ty][tx]==1 ){
	  last |= (1<<num[ty][tx]);
	}
      }
    }
#if DEB
    printf("sz:%d\n",v.size());
    printf("last:%d\n",last);
    rep(i,v.size()){
      printf("home:%d  , %d\n",i,kari[i]);
    }
#endif
    
    

    printf("%d\n",dfs(sx,sy,0));
  }
  

  return 0;
}