rows rows and cols columns. Rows are numbered from 1 to rows, columns from 1 to cols, and a cell is written as [row, column].
In one move the rook goes to any other cell in the same row or the same column (any distance; nothing blocks it). It cannot stay where it is.
Count the ways the rook can get from cell start to cell finish in exactly moves moves. Two ways differ if their sequences of visited cells differ; the route may pass through any cells, including start and finish. The answer can be huge, so return it modulo 10⁹ + 7.rows=2, cols=3, moves=2, start=[1, 1], finish=[2, 3] → 2
Two routes work: (1,1) → (1,3) → (2,3) and (1,1) → (2,1) → (2,3).
rows=2, cols=2, moves=2, start=[1, 1], finish=[1, 1] → 2
You can go to (1,2) and come back, or go to (2,1) and come back: two routes.
rows=4, cols=5, moves=1, start=[2, 2], finish=[3, 4] → 0
The cells share neither a row nor a column, so one move cannot get there.
rows, cols ≤ 10⁹moves ≤ 10⁵len(start) = len(finish) = 2start[0], finish[0] ≤ rowsstart[1], finish[1] ≤ colsrows=2, cols=3, moves=2, start=[1, 1], finish=[2, 3]
2
Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.