미로 탈출 경로

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

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

입출력 예시