A courier must deliver a package across a city. The city’s streets form a rectangular grid with horizontal streets and vertical streets. On the city map, the horizontal streets are numbered from to from top to bottom, and the vertical streets from to from left to right. Intersection is where horizontal street meets vertical street . The courier starts at and must deliver the package at .
In one move, the courier can follow a street from to an adjacent intersection:
Down, to ;
Up, to ;
Right, to ; or
Left, to .
The courier may only travel between intersections in this grid.
The courier is in no hurry to finish the delivery. To make the trip last longer, they want to choose a route that includes exactly Up moves and exactly Left moves. The courier is willing to visit any intersection more than once, including the starting and ending intersections.
Count the number of different routes from to that stay within the grid and contain exactly Up moves and exactly Left moves. Two routes are considered different if their sequences of moves are different.
The input consists of a single line that contains four integers , , and ( and ), indicating respectively the number of horizontal streets, the number of vertical streets, the required number of Up moves, and the required number of Left moves.
Output a single line with an integer indicating the number of valid routes. Since this number can be large, output the remainder of dividing it by .
2 2 1 0
4
Each route uses two Down moves, one Up move, and one Right move. Writing directions by their first letters, the four routes are DUDR, DURD, DRUD, and RDUD. The first two routes visit the starting intersection twice, while the last two routes visit the destination twice.
3 3 1 1
280
2 163 2 0
20719340