로봇 청소기가 \(N \times M\) 격자의 왼쪽 위 칸 \((1,1)\) 에서 출발해 오른쪽 아래 칸 \((N,M)\) 으로 가려고 한다. 로봇은 한 번에 오른쪽 또는 아래쪽 으로만 한 칸 이동할 수 있다.

격자에는 가구가 놓인 칸(장애물)이 있어 그 칸은 지날 수 없다. 출발 칸에서 도착 칸까지 가는 서로 다른 경로의 수를 구하여라.

경로의 수가 클 수 있으므로 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력한다. 출발 칸이나 도착 칸이 장애물이면 경로 수는 \(0\) 이다.

• \(1 \le N, M \le 1{,}000\)
• 격자의 각 값은 \(0\) 또는 \(1\) 이다.

첫째 줄에 격자의 행 수 \(N\) 과 열 수 \(M\) 이 주어진다.

이어지는 \(N\) 개의 줄에 각각 \(M\) 개의 정수가 주어지며, \(0\) 은 빈 칸, \(1\) 은 장애물을 의미한다.

경로의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original