격자상의 경로 timer 1초 memory 64MB

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M 까지의 번호가 첫 행부터 시작하여 차례로 부여 되어 있다. 

격자의 어떤 칸은 Ｏ 표시가 되어 있다. (단,1번 칸과 N×M 번 칸은 Ｏ 표시가 되어 있지 않다. 

또한, Ｏ 표시가 되어 있는 칸은 최대 한 개이다. 즉, Ｏ 표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 

이 격자에서는 8번 칸에 Ｏ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M 번 칸으로 가고자 한다.

조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)

조건 2: 격자에 Ｏ로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

1 → 2 → 3 → 8 → 9 → 10 → 15

1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 

이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.