质数行者

游戏在一个 n \times m \times w 的立体方格图上进行, 从北到南依次标号为第 1 行到 第 n 行, 从西到东依次标号为第 1 列到第 m 列, 从下到上依次标号为第 1 层到 第 w 层。

小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w 层。每一步, 他可以向东走质数格、向南走质数格或者向上走质数格。每走到 一个位置, 小蓝的角色要稍作停留。

在游戏中有两个陷阱, 分别为第 $r{1} 行第 c{1} 列第 h{1} 层和第 r{2} 行第 c{2} 列第 h{2}$ 层。这两个陷阱的位置可以跨过, 但不能停留。也就是说, 小蓝不能控制角 色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。

小蓝最近比较清闲, 因此他想用不同的走法来完成这个游戏。所谓两个走法不同, 是指小蓝稍作停留的位置集合不同。

请帮小蓝计算一下，他总共有多少种不同的走法。

提示：请注意内存限制, 如果你的程序运行时超过内存限制将不得分。

输入第一行包含两个整数 n, m, w, 表示方格图的大小。

第二行包含 6 个整数, $r{1}, c{1}, h{1}, r{2}, c{2}, h{2}$ ，表示陷阱的位置。

输出一行, 包含一个整数, 表示走法的数量。答案可能非常大, 请输出答 案除以 1000000007（即 10^9+7） 的余数。

【样例说明】

用 (r, c, h) 表示第 r 行第 c 列第 h 层, 可能的走法有以下几种:

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) 。

【评测用例规模与约定】

对于 30 \% 的评测用例 1 \leq n, m, w \leq 50 。

对于 60 \% 的评测用例 1 \leq n, m, w \leq 300 。

对于所有评测用例, $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$, 陷阱不在起点或终点, 两个陷阱不同。

蓝桥杯 2020 年