산타클로스와 루돌프

산타클로스는 노원구에 살고있는 모든 아이들에게 선물을 나누어 주려고 한다. 노원구에 있는 모든 집에는 아이가 있기 때문에, 산타클로스는 모든 집에 선물을 나누어 주어야 한다. 올해 산타가 타고 다닐 루돌프는 길치라서 건물 이외의 장소에는 내릴 수 없다. 따라서, 산타는 선물을 나누어줄 방법을 연구하려고 한다.

노원구는 1*1 크기의 영역으로 나누어져 있고, 각 영역은 집, 교회, 공터 중 하나이다. 노원구에는 교회가 하나 있다. 산타클로스와 루돌프는 교회에서 출발하여 모든 집에 선물을 나누어 주고, 다시 교회로 돌아가려고 한다. 또, 다음 규칙을 지켜야 한다.

1. 루돌프는 동서남북 방향으로만 날 수 있다. 또, 공중에서 방향 전환을 할 수 없다.
2. 아직 선물을 나누어 주지 않은 집은 자유롭게 통과할 수 있다. 아직 선물을 주지 않은 집에 내려갔다면, 그 집에 선물을 나누어 주어야 하고, 다시 동서남북 방향 중 한 방향으로 날아 오른다.
3. 노원구의 모든 집에는 벽난로가 있다. 산타가 오기 전에는 벽난로에 불을 붙이지 않는다. 산타는 같은 집에 선물을 두 번 나누어 주지 않기 위해, 날아 오를때 벽난로에 불을 붙인다. 따라서, 벽난로에 불을 붙이면 굴뚝에서 연기가 나오므로, 선물을 나누어 준 집 위를 통과할 수 없다.
4. 교회는 자유롭게 통과할 수 있다. 하지만, 교회에서는 예배가 있기 때문에, 모든 선물을 나누어 주기 전까지 교회에 내릴 수 없다.
5. 공터 위는 자유롭게 통과할 수 있다. 하지만, 공터에 내릴 수는 없다.

도시의 구조가 주어졌을 때, 산타와 루돌프가 선물을 나누어주는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 마을의 가로 크기 m과 세로 크기 n이 주어진다. (1 ≤ m, n ≤ 10) 다음 n개 줄은 m개의 수가 공백으로 구분되어 주어진다. 각 수는 그 구역의 상태이며, 0, 1, 2중 하나이다. 0인 경우에는 공터, 집인 경우에는 1, 교회인 경우에는 2가 된다. 교회는 항상 1개이며, 집의 개수는 1개 이상, 23개 이하이다.

첫째 줄에 선물을 나누어 줄 수 있는 방법의 수를 출력한다. 이 값은 2000000보다 작거나 같다.