Unique Paths in a Maze

You are given a maze represented as a $N \times M$ grid. In the maze, there are $T$ obstacles, and the obstacle cells are impassable. You are allowed to move in the four cardinal directions: up, down, left, and right; each move takes you one cell. Each cell can be visited at most once in a single path. Given the starting coordinates and the target coordinates, determine the number of distinct paths from the start to the target. It is guaranteed that the start cell does not contain an obstacle.

inputFormat

The input begins with three integers separated by spaces: $N$, $M$, and $T$, representing the number of rows, columns, and obstacles respectively.

Then follow $T$ lines, each containing two integers $r$ and $c$ (1-indexed) which denote the coordinates of an obstacle cell.

Next, a line follows with two integers $s_x$ and $s_y$, representing the starting cell's coordinates.

Finally, a line with two integers $t_x$ and $t_y$ is given, representing the target cell's coordinates.

outputFormat

Output a single integer representing the number of distinct paths from the starting cell to the target cell under the given constraints.

sample

2 2 0
1 1
2 2

2