Problem A

How many ways?

You are to count the number of ways in which you can cross a minefield. The minefield is provided. You can start at any of the northernmost sqruares, and at each step you can move to the south, the southwest, or the southeast. You are not allowed to start from a location that has a mine on it or to move into a location with a mine. You cannot go out of the map area - there are rivers on both sides. The minefield is considered crossed once you have reached any of the southernmost squares of the map.

Input format

Each test case will start with two numbers, r and c - the number of rows and columns in the map. Then r lines, c characters each, will follow. The only characters on the map will be '.' (empty space) and '#' (mine). The first row represents the northern boundary of the minefield and the last row represents the southern boundary. Both r and c will be at most 30.

Output format

For each test case, output a single integer on a separate line: the number of different ways to cross the minefield as described above. It's guaranteed that the answer will fit into 64 bit integer (C++ long long, Java long).

Sample input

6 5
.....
..##.
.....
.#.#.
..#..
.....
10 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........

Sample output

130
136946