올해도 산타클로스가 하늘에서 JOI 마을로 왔다. JOI 마을의 모든 집에는 아이가 있어서, 산타는 모든 집에 선물을 돌려야 한다. 올해 데려온 순록은 조금 방향치이고, 건물 위가 아니면 내릴 수 없어서 길을 잘 짜야 한다. JOI 마을은 동서남북으로 구획이 나뉘어 있고, 각 칸은 집, 교회, 빈터 중 하나이다. 교회는 하나뿐이다. 다음 규칙을 따라 산타와 순록은 교회에서 출발해 모든 집에 선물을 한 번씩 나른 뒤 교회로 돌아온다. 올해 순록은 동서남북 가운데 한 방향으로만 곧게 날 수 있고, 공중에서는 방향을 바꿀 수 없다. 아직 선물을 주지 않은 집 위는 자유롭게 지나갈 수 있다. 아직 선물을 주지 않은 집에는 내릴 수 있다. 집에 내리면 반드시 선물을 주고, 그다음에는 동서남북 가운데 한 방향으로 떠난다. JOI 마을의 집은 산타가 올 때까지 난로를 켜지 않지만, 산타가 떠난 뒤에는 난로를 켠다. 난로를 켜면 굴뚝에서 연기가 나와, 선물을 이미 준 집 위는 지나갈 수 없다. 교회 위는 자유롭게 지나갈 수 있다. 다만 교회에서 예배가 진행 중이므로, 모든 선물을 다 주기 전에는 교회에 내릴 수 없다. 빈터 위는 자유롭게 지나갈 수 있지만, 빈터에는 내릴 수 없다. 마을의 구조가 주어질 때, 산타와 순록이 선물을 나르는 경로가 몇 가지인지 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(m\) \(n\)
\(c_{1,1}\) \(c_{1,2}\) \(\cdots\) \(c_{1,m}\)
\(\vdots\)
\(c_{n,1}\) \(c_{n,2}\) \(\cdots\) \(c_{n,m}\)
- 입력은 \(n+1\)줄이다.
- 첫째 줄에 정수 \(m\)과 \(n\)이 공백 하나로 구분되어 주어진다.
- 둘째 줄부터 \(n+1\)번째 줄까지, 각 줄에 \(0\), \(1\), \(2\) 중 하나가 공백 하나로 구분되어 \(m\)개 주어진다.
- 북쪽에서 \(i\)번째, 서쪽에서 \(j\)번째 칸을 \((i,j)\)라 하면(\(1 \le i \le n\), \(1 \le j \le m\)), \(i+1\)번째 줄의 \(j\)번째 값은 칸 \((i,j)\)가 빈터이면 \(0\), 집이면 \(1\), 교회이면 \(2\)이다.
- \(1 \le m \le 10\)
- \(1 \le n \le 10\)
- 교회는 \(1\)개이고, 집은 \(1\)개 이상 \(23\)개 이하이다.
- 채점용 입력에서 경로 수는 \(2000000\)을 넘지 않는다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 선물을 나르는 경로의 수를 출력한다.