Routes around blocked cells

Problem

A delivery robot moves from the top-left to the bottom-right cell of a grid, one step right or down. Cells marked # are blocked. Count the routes with a cached recursion.

Input, output and limits

Input: Line 1: rows and columns. Then one line per row of . (free) and # (blocked) characters.
Output: One integer: the number of routes.
Constraints: 1 ≤ rows, columns ≤ 14
The first and last cells may be blocked

Examples

Example

Input

3 3
...
.#.
...

Output

Two routes go around the block.

Hints

Try the problem first. Open one hint at a time.

Hint 1

The routes to a cell are the routes to the cell above plus those to the cell on the left.

Hint 2

A blocked or outside cell has 0 routes.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Count inversionshard
Ways to make a paymenthard
Binomial coefficientmedium
Longest common subsequencehard
Merge sortmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Recursion in Depth problems

Problem

Input, output and limits

Examples

Hints

More Recursion in Depth problems