잭은 매일 오후에 자기 집에서 존의 집까지 달린다. 두 집은 N행 M열 크기의 들판에 있다. 잭은 날마다 다른 길로 가고 싶어 하지만 서로 다른 길이 몇 가지인지는 모른다.
들판은 다음과 같이 N행 M열 격자로 나타낸다.
....
..X.
....
잭은 왼쪽 위 칸에 살고 존은 오른쪽 아래 칸에 산다. 잭은 시간을 낭비하기 싫어서 아래쪽과 오른쪽으로만 이동한다. 들판의 일부 칸에는 바위나 건물 같은 장애물이 있고, 잭은 그 칸을 지나갈 수 없다. 장애물은 X로 표시한다.
위 들판에서 갈 수 있는 경로는 다음 4가지다. 경로가 지나는 칸을 별표로 표시했다.
**** *... *... **..
..X* *.X. **X. .*X.
...* **** .*** .***
어떤 경로든 길이는 항상 N + M - 1로 같다.
경로의 수가 매우 커질 수 있으므로 1000000007 (109+7)로 나눈 나머지를 출력한다.