Prime Steps 3D Maze

In this problem, you are given a 3D grid of dimensions $n \times m \times w$. The rows are numbered from $1$ to $n$ (from north to south), the columns from $1$ to $m$ (from west to east), and the layers from $1$ to $w$ (from bottom to top).

Little Blue wants to move his character from the starting cell $(1,1,1)$ to the destination cell $(n,m,w)$. At every step, he may move a number of cells equal to a prime number in one of the three positive directions: east (increasing column), south (increasing row) or up (increasing layer). That is, in one step he can move from cell $(i,j,k)$ to one of the following, provided the new cell lies within the grid:

• East: $(i, j+p, k)$
• South: $(i+p, j, k)$
• Up: $(i, j, k+p)$

There are two traps in the game located at $(r_1, c_1, h_1)$ and $(r_2, c_2, h_2)$. Although Little Blue can cross over a trap in the middle of a move, he is not allowed to stop (i.e. land) on a trap cell.

Two routes are considered different if the set of cells at which Little Blue stops (including the start and destination) are different. Your task is to compute the total number of distinct ways to complete the game.

Note: Use efficient memory management as the grid dimensions might be large.

inputFormat

The input consists of two lines:

The first line contains three integers $n$, $m$, $w$ representing the dimensions of the grid.
The second line contains six integers: $r_1$, $c_1$, $h_1$, $r_2$, $c_2$, $h_2$, which are the coordinates of the two trap cells.

It is guaranteed that the starting cell $(1,1,1)$ and the destination cell $(n,m,w)$ are not traps.

outputFormat

Output a single integer representing the total number of distinct ways to go from $(1,1,1)$ to $(n,m,w)$ following the rules.

sample

3 3 3
1 3 1 3 1 3

2