Tojaengi's Walk to School
Time limit1sMemory limit128 MB
Count monotone lattice paths from (1,1) to (w,h) that pass through a given shop, modulo 1000007.
- Level
Easy2 of 10
- Topics
- Combinatorics, Math
- Solved
- No attempts yet
Problem
Tojaengi studies at Inha University and lives in a city with roads parallel to the y axis and roads parallel to the x axis. Each place where two roads meet is written as a coordinate : it is the crossing of the -th vertical road from the left and the -th horizontal road from the bottom. Tojaengi's house is at the bottom left corner and the school is at the top right corner . Travelling between two neighbouring crossings takes the same time on every block.
Every morning Tojaengi walks to school and stops at a toast shop on the way. Tojaengi likes to dawdle and leaves just late enough to arrive exactly when class starts, so the route from the house through the toast shop to the school always has to be a route that takes the least possible time. Making the toast and eating it both take 0 seconds.
The picture below shows the city for and .

If the toast shop is at , there are exactly two least-time routes from the house through the shop to the school .

Given the position of the toast shop, count the routes on which Tojaengi reaches school without being late.
Input
The first line contains the number of roads parallel to the y axis, , and the number of roads parallel to the x axis, , separated by a space. ()
The second line contains the coordinates and of the toast shop, separated by a space. (, ) Both and are integers.
Output
Print the number of routes to school modulo 1000007 on the first line.