Counting Distinct Shortest Paths

You are given a grid represented as a matrix of integers, where 0 indicates an open cell and 1 indicates an obstacle. Your task is to compute the number of distinct shortest paths from a given starting cell to a target cell. Movement is allowed in four directions: up, down, left, and right.

Let \(d\) be the shortest distance from the start to the target in terms of number of moves. Two paths are considered distinct if the sequence of visited cells is different. If no valid path exists, the answer is 0.

Input/Output Format: Read input from stdin and print the result to stdout.

inputFormat

The input consists of:

1. A line containing two integers \(r\) and \(c\), representing the number of rows and columns of the grid.
2. \(r\) lines follow, each containing \(c\) space-separated integers (each is either 0 or 1), representing the grid.
3. A line with two integers representing the starting cell coordinates (row and column, 0-indexed).
4. A line with two integers representing the target cell coordinates (row and column, 0-indexed).

You may assume that the starting and target cells are always within the grid boundaries.

outputFormat

Print a single integer: the number of distinct shortest paths from the starting cell to the target cell. If the target is unreachable, print 0.

4 4
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
0 0
3 3

2