CMPUT 275 - Tangible Computing
Morning Problem: University Navigation
Description
Natali has spent all of today figuring out the most efficient routes to go back and forth
between her classes. She thinks she’s figured out the best way to get between math 118 and
math 227, but she wonders how many possible routes there are for her to take.
She’s modeled the area between her math 118 class and her math 227 class as a grid, with
math 118 at the top left and math 227 at the bottom right. She starts at the top left and can
move either down or to the right until she hits the bottom right. She’s curious how many
different sequences of down and right moves exist that will allow her to reach math 227. For
example, if Natali is on a 2x2 grid, there are 6 possible ways for her to get from the top left
to the bottom right:
Given an mxn grid, how many ways are there for Natali to go from the top left to the bottom right? Report your answer modulo 4,201,337 (since the number will get very large very
quickly otherwise.)
Hint: Consider using dynamic programming, note the only ways to reach a position
(i, j) are through either (i − 1, j) or (i, j − 1) if i, j 0.
Input
Input consists of one line with two integers n and m (1 ≤ n, m ≤ 500), denoting the height
and width of the grid.
Output
Print one integer denoting the number of ways Natali can go from the top left of the grid to
the bottom right, modulo 4,201,337.
Sample Input 1
2 2
Sample Output 1
6
Sample Input 2
2 5
Sample Output 2
21
Sample Input 3
3 3
Sample Output 3
20
