경로 세기

격자의 왼쪽 위에서 오른쪽 아래로 오른쪽이나 아래로만 이동하며 장애물 칸을 피하는 경로의 수를 10^9 + 7로 나눈 나머지로 구한다.

보통4동적 계획법행렬아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

잭은 매일 오후에 자기 집에서 존의 집까지 달린다. 두 집은 N행 M열 크기의 들판에 있다. 잭은 날마다 다른 길로 가고 싶어 하지만 서로 다른 길이 몇 가지인지는 모른다.

들판은 다음과 같이 N행 M열 격자로 나타낸다.

....
..X.
....

잭은 왼쪽 위 칸에 살고 존은 오른쪽 아래 칸에 산다. 잭은 시간을 낭비하기 싫어서 아래쪽과 오른쪽으로만 이동한다. 들판의 일부 칸에는 바위나 건물 같은 장애물이 있고, 잭은 그 칸을 지나갈 수 없다. 장애물은 X로 표시한다.

위 들판에서 갈 수 있는 경로는 다음 4가지다. 경로가 지나는 칸을 별표로 표시했다.

****      *...      *...      **..
..X*      *.X.      **X.      .*X.
...*      ****      .***      .***

어떤 경로든 길이는 항상 N + M - 1로 같다.

경로의 수가 매우 커질 수 있으므로 1000000007 (109+710^9 + 7)로 나눈 나머지를 출력한다.

입력

첫째 줄에 들판의 행 개수 N과 열 개수 M이 주어진다.

다음 N개 줄에는 각각 M개의 문자가 주어진다. 문자가 점(.)이면 빈 칸이고, X이면 장애물이 있어서 잭이 지나갈 수 없는 칸이다.

왼쪽 위 칸과 오른쪽 아래 칸에는 장애물이 없다.

2N2002 \le N \le 200

2M2002 \le M \le 200

출력

왼쪽 위 칸에서 오른쪽 아래 칸까지 가는 경로의 수를 1000000007로 나눈 나머지를 출력한다.

대부분의 언어에서 나머지 연산자는 %다.