• 117

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

Your city is a rectangular grid of buildings with streets joining them vertically and horizontally.
All the streets are one way: you can only go either south or east, but never north or west.

Your program has to compute the number of routes linking the North-West corner to the South-East one in an M x N city grid.

Be warned however that OneWay City is in fact a Megalopolisâ€”with all the headaches that it implies. Actually, the numbers can get so big that your program's output should only contain the first 1000 digits of the solution.
Input
Line 1: M, the number of west-east roads
Line 2: N, the number of north-south roads
Output
Number of ways leading from the North-West corner to the South-East one, truncated to the most significant 1000 digits.
Constraints
0 < N, M <= 5000
Example
Input
```4
4```
Output
`20`

A higher resolution is required to access the IDE