题目背景

小蓝在玩一个叫质数行者的游戏。

题目描述

游戏在一个 $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$） 的余数。

5 6 1
3 4 1 1 2 1

11

提示

【样例说明】

用 $(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 年国赛 B 组 J 题。