题目描述

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

游戏在一个 $n×m×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$，表示陷阱的位置。

其中有 ，$1≤n,m,w≤1000，1≤r_1,r_2≤n，1≤c_1,c_2≤m，1≤h_1,h_2≤w$，陷阱不在起点或终点，两个陷阱不同。

输出描述

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

5 6 1
3 4 1 1 2 1

11

样例说明

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

(1, 1, 1) − (1, 3, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
(1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
(1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
(1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
(1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
(1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 3, 1) − (5, 6, 1)。
(1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 4, 1) − (5, 6, 1)。
(1, 1, 1) − (1, 4, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
(1, 1, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
(1, 1, 1) − (3, 1, 1) − (3, 6, 1) − (5, 6, 1)。
(1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 6, 1)。

评测用例规模与约定：

对于 30% 的评测用例，$1≤n,m,w≤50$。

对于 60% 的评测用例，$1≤n,m,w≤300$。

对于所有评测用例，$1≤n,m,w≤1000，1≤r_1,r_2≤n，1≤c_1,c_2≤m，1≤h_1,h_2≤w$，陷阱不在起点或终点，两个陷阱不同。