Problem Description
Ranald the cat is coding a flybot today! The main objective of this flybot is to get from the top left hand corner of the wall to the bottom right hand corner. The flybot will be at the top left hand corner initially.
Walls are described using a grid system where each cell represents a centimetre square, where by '.' denotes a empty section of a wall and 'X' denotes an object (such as posters or pictures pinned to the wall). The flybot cannot pass through such objects.
The flybot can only move right since it is poorly coded, it also can only move downwards as it does not have enough power to overcome gravity.
Ranald the cat wonders how many different routes are there for his flybot to complete its objective. As this number can be very huge, he just needs to know the remainder of that number when divided by 1000000007.
It should be also noted that the top left hand corner and the bottom right hand corner of the wall will only be '.' and not 'X'.
Input
The first line of input contains H and W, which is the height and width of the wall in centimeteres respectively.
The following H lines of input will contain W characters each, either '.' or 'X'. These lines describe Ranald the cat's wall.
Output
A single integer, the remainder of the number of ways Ranald's flybot can complete its objective when divided by 1000000007.
Limits
Subtask 1 (30%): 0 < H, W ≤ 10.
Subtask 2 (20%): 0 < H, W ≤ 100.
Subtask 3 (20%): 0 < H, W ≤ 1000. However, the grid will only contain '.'s.
Subtask 4 (30%): 0 < H, W ≤ 1000. The grid will contain both 'X's and '.'s.
Sample Input 1
3 3
...
...
...
Sample Output 1
6
Sample Input 2
3 3
.X.
.X.
...
Sample Output 2
1
Sample Input 3
3 3
...
.X.
...
Sample Output 3
2