Description

Given an $N \times M$ grid maze with $T$ obstacles, where obstacle cells are impassable.

Movement is allowed in four directions: up, down, left, and right, moving exactly one cell per step. It is guaranteed that the starting cell has no obstacle.

Given the start coordinates and the end coordinates, with each cell visited at most once, find the number of different paths from the start to the end.

Input Format

The first line contains three positive integers $N, M, T$, representing the numbers of rows and columns of the maze and the total number of obstacles.

The second line contains four positive integers $SX, SY, FX, FY$. $SX, SY$ are the start coordinates, and $FX, FY$ are the end coordinates.

The next $T$ lines each contain two positive integers, representing the coordinates of an obstacle.

Output Format

Output the total number of paths from the start to the end.

2 2 1
1 1 2 2
1 2

1

Hint

For $100\%$ of the testdata, $1 \le N, M \le 5$, $1 \le T \le 10$, $1 \le SX, FX \le N$, $1 \le SY, FY \le M$.

Translated by ChatGPT 5