Mushroom Land is represented by a grid of N by M grid squares. Each grid square can be empty, '.', or an obstacle, '#'. A dog and a cat start on the top left corner of Mushroom Land, and wishes to get to the bottom right corner of Mushroom Land. At each step, they are allowed to move down or right, but as they do not like each other, their paths cannot intersect other than at the start and end points, i.e. they cannot be on the same square. Help them figure out how many possible ways both of them can travel this journey, while meeting such a condition, modulo 109 + 7.
The first line of input will contain two integers, N and M.
The next N lines of input will contain M characters each, representing the grid. It is guaranteed that the top left and bottom right corner squares are empty.
The output should contain one line with one integer, the total number of ways the above scenario could occur, modulo 109 + 7.
Subtask 1 (27%): 3 ≤ N, M ≤ 70.
Subtask 2 (33%): 3 ≤ N, M ≤ 300.
Subtask 3 (40%): 3 ≤ N, M ≤ 2000.
Subtask 4 (0%): Sample Testcases.
Sample Input 1
Sample Output 1
Explanation for Sample 1
The dog can take the top path from top-left to bottom-right, and the cat can take the bottom path from top-left to bottom-right. The two can swap roles as well.
Sample Input 2
Sample Output 2
Explanation for Sample 2
The animal that takes the top path has only one path, the bottom animal has two possible paths.