Count monotone lattice paths from (1,1) to (w,h) that pass through a given shop, modulo 1000007.
Easy2CombinatoricsMathNo attempts yetTime limit1sMemory limit128 MBTojaengi studies at Inha University and lives in a city with w roads parallel to the y axis and h roads parallel to the x axis. Each place where two roads meet is written as a coordinate (x,y): it is the crossing of the x-th vertical road from the left and the y-th horizontal road from the bottom. Tojaengi's house is at the bottom left corner (1,1) and the school is at the top right corner (w,h). 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 w=3 and h=2.

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

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