Consider the 'map' below of Farmer John's milk delivery service. It has N (2 <= N <= 100) rows and M ( 2 <= M <= 80) columns.
. . . . . . . T
. . . . . . C .
. . . . C S . .
. S . . C . S .
D C . . S . . .
Farmer John delivers milk to his rural customers (denoted as 'C') as he travels from the dairy (denoted as 'D' and always located in the lower left hand corner) to the town (denoted as 'T' and always located in the upper right corner). He traverses roads on the square grid by moving either horizontally to the right or vertically toward the top, never diagonally.
FJ never travels toward the left or toward the bottom of his map. Some roads are blocked by snow (denoted as 'S') which means FJ can not traverse that square.
Write a program that cowculates the total number of different milk routes available from the dairy to the town. Two routes are different if they differ on any part of the path. FJ routes are always arranged so that all
customers can be reached while moving north and east. The total number of different milk routes will fit in a 32-bit signed integer.