Wall-bounce paths: hints, no solution

A drone starts on one cell of a grid of garden beds with rows rows and cols columns, given as start = [row, column] with both counted from 0. On each move it flies one cell up, down, left or right. A flight path is a sequence of exactly moves moves that stays inside the grid until the very last move and leaves the grid on that last move. Return the number of different flight paths, modulo 1000000007. Two paths differ if some move differs. A sequence that leaves the grid earlier is not counted.

Examples

Input

rows = 2, cols = 2, moves = 1, start = [0, 0]

Output

2

Note

Flying up or left leaves the grid.

Input

rows = 1, cols = 1, moves = 2, start = [0, 0]

Output

0

Note

Every first move already leaves the grid.

Input

rows = 1, cols = 3, moves = 2, start = [0, 1]

Output

6

Note

Only left or right stays inside first, then three directions leave from an end cell.

Constraints

• 1 <= rows, cols <= 40
• 1 <= moves <= 400
• start is a cell inside the grid

Hint 1: a nudge

The number of ways to reach a cell after some moves does not depend on how you got there beyond the counts. What could you record for every cell after each move?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing