Challenge: Paths in a Grid

Lab Python Intermediate 20 points

A robot starts at the top-left of a grid with r rows and c columns and must reach the bottom-right. It can only move right or down. Print how many different paths there are. Use recursion with memoization.

Input

Two whole numbers r c (1 ≤ r, c ≤ 16).

Output

The number of paths.

Example

Input

2 2

Output

Sample input available Sample output available

Editor

Python

Hints

A grid with one row or one column has exactly 1 path.

Every path's first move is right or down: paths(r, c) = paths(r - 1, c) + paths(r, c - 1).

Add @lru_cache (from functools) to remember answers.

Solution explanation

Without memoization the same sub-grids are counted again and again; with it, each (r, c) is solved once.

Show solution

from functools import lru_cache

@lru_cache(maxsize=None)
def paths(r, c):
    if r == 1 or c == 1:
        return 1
    return paths(r - 1, c) + paths(r, c - 1)

r, c = map(int, input().split())
print(paths(r, c))

Output

Answer