미로 탈출 경로

N행 M열의 격자 미로가 있다. 일부 칸은 벽으로 막혀 있어 지나갈 수 없다. 벽이 아닌 모든 칸은 반드시 한 번씩 방문해야 하는데, 상하좌우로 인접한 칸으로만 이동할 수 있다.

시작점 (0, 0)에서 출발하여 도착점 (N-1, M-1)에 도달하면서, 벽이 아닌 모든 칸을 정확히 한 번씩 방문하는 경로의 수를 구하시오.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (2 <= N, M <= 7)
둘째 줄부터 N개의 줄에 걸쳐 미로의 정보가 주어진다. 각 줄은 M개의 정수로 이루어져 있다. 0은 빈 칸, 1은 벽을 의미한다. 시작점 (0, 0)과 도착점 (N-1, M-1)은 항상 빈 칸이다.

출력

조건을 만족하는 경로의 수를 출력한다.

입출력 예시

입력 1

3 3
0 0 0
0 0 0
0 0 0

출력 1

2

입력 2

2 3
0 0 0
0 0 0

출력 2

1