Loading...
Loading...
Loading...
Ananya walks from her hostel to the college library every morning. The lanes between them form a grid of r rows and c columns of crossings. The hostel is at the top-left crossing and the library is at the bottom-right crossing.
She never walks away from the library, so every step takes her one crossing to the right or one crossing down. Two routes are different if they pass through a different set of crossings.
Print the number of different routes. The count can be huge, so print it modulo 10^9 + 7.
Example 1
Input
3 3
Output
6
Each route makes 2 steps right and 2 steps down in some order. There are 6 orders.
Example 2
Input
3 4
Output
10
Each route has 3 steps right and 2 steps down, which gives 10 routes.
Try the problem first. Open one hint at a time.
The last step into any crossing comes either from the crossing just above it or from the crossing just to its left.
So the routes to a crossing are the routes to the crossing above plus the routes to the crossing on the left.
Every crossing in the top row or the left column has exactly one route.
Fill a table row by row, left to right, and take the remainder modulo 10^9 + 7 after each addition.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor