A sorting-center floor is laid out as a grid with rows rows and cols columns. A pallet robot starts in the top-left cell (0, 0) and must reach the bottom-right cell (rows-1, cols-1). On every move the robot goes either one cell right or one cell down; it can never move left, up, or diagonally. Some cells are blocked by shelving, and the robot can never enter a blocked cell. For a compliance audit, the robot's route must also pass through one specific checkpoint cell at some point during the trip (the checkpoint may be the start cell, the end cell, or any cell in between).
Input format
Line 1: two integers rows and cols.
Each of the next rows lines: cols space-separated integers, each 0 (clear) or 1 (blocked), giving the floor row by row.
Last line: two integers cr and cc -- the 0-indexed row and column of the mandatory checkpoint cell.
Output format
Print a single integer: the number of distinct right/down routes from (0, 0) to (rows-1, cols-1) that never enter a blocked cell and that visit the checkpoint cell (cr, cc) at some point, taken modulo 1000000007. If no such route exists (including when the start, end, or checkpoint cell is itself blocked), print 0.
Constraints
- 1 <= rows, cols <= 40
- 0 <= cr < rows, 0 <= cc < cols
- Each grid cell is
0or1