Background

Xiao Lan is playing a game called Prime Walker.

Problem Description

The game is played on a 3D grid of size $n \times m \times w$. Rows are numbered from north to south as Row $1$ to Row $n$, columns are numbered from west to east as Column $1$ to Column $m$, and layers are numbered from bottom to top as Layer $1$ to Layer $w$.

Xiao Lan needs to control his character to move from Row $1$, Column $1$, Layer $1$ to Row $n$, Column $m$, Layer $w$. At each step, he may move east by a prime number of cells, move south by a prime number of cells, or move up by a prime number of cells. Each time he reaches a position, Xiao Lan’s character must stop there briefly.

There are two traps in the game, located at Row $r_{1}$, Column $c_{1}$, Layer $h_{1}$ and Row $r_{2}$, Column $c_{2}$, Layer $h_{2}$. These trap positions may be crossed over, but the character is not allowed to stop on them. That is, Xiao Lan cannot make a move that lands exactly on a trap, but it is allowed for a move to pass over a trap in the middle.

Xiao Lan has been quite free recently, so he wants to finish the game in different ways. Two ways are considered different if the sets of positions where Xiao Lan stops briefly are different.

Please help Xiao Lan compute how many different ways there are in total.

Note: Please pay attention to the memory limit. If your program exceeds the memory limit during execution, it will receive zero points.

Input Format

The first line contains three integers $n, m, w$, representing the size of the grid.

The second line contains $6$ integers $r_{1}, c_{1}, h_{1}, r_{2}, c_{2}, h_{2}$, representing the positions of the traps.

Output Format

Output one line containing one integer, representing the number of ways. The answer may be very large. Please output the remainder of the answer modulo $1000000007$ (i.e. $10^9+7$).

5 6 1
3 4 1 1 2 1

11

Hint

Sample Explanation

Use $(r, c, h)$ to represent Row $r$, Column $c$, Layer $h$. The possible ways are as follows:

1. $(1,1,1)-(1,3,1)-(1,6,1)-(3,6,1)-(5,6,1)$.

2. $(1,1,1)-(1,3,1)-(3,3,1)-(3,6,1)-(5,6,1)$.

3. $(1,1,1)-(1,3,1)-(3,3,1)-(5,3,1)-(5,6,1)$.

4. $(1,1,1)-(3,1,1)-(3,3,1)-(3,6,1)-(5,6,1)$.

5. $(1,1,1)-(3,1,1)-(3,3,1)-(5,3,1)-(5,6,1)$.

6. $(1,1,1)-(3,1,1)-(5,1,1)-(5,3,1)-(5,6,1)$.

7. $(1,1,1)-(3,1,1)-(5,1,1)-(5,4,1)-(5,6,1)$.

8. $(1,1,1)-(1,4,1)-(1,6,1)-(3,6,1)-(5,6,1)$.

9. $(1,1,1)-(1,6,1)-(3,6,1)-(5,6,1)$.

10. $(1,1,1)-(3,1,1)-(3,6,1)-(5,6,1)$.

11. $(1,1,1)-(3,1,1)-(5,1,1)-(5,6,1)$.

Constraints and Assumptions

For $30\%$ of the testdata, $1 \leq n, m, w \leq 50$.

For $60\%$ of the testdata, $1 \leq n, m, w \leq 300$.

For all testdata, $1 \leq n, m, w \leq 1000$, $1 \leq r_{1}, r_{2} \leq n$, $1 \leq c_{1}, c_{2} \leq m$, $1 \leq h_{1}, h_{2} \leq w$. The traps are not at the start or the end, and the two traps are different.

Lanqiao Cup 2020 National Contest B Group, Problem J.

Translated by ChatGPT 5