质数行者

题目描述

小蓝在玩一个叫质数行者的游戏，游戏在一个 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 66 个整数，r 1 , c 1 , h 1 , r 2 , c 2 , h 2  表示陷阱的位置。

输出格式

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

样例输入

5 6 1

3 4 1 1 2 1

样例输出

11

样例说明

用 ( r , c , h ) (r,c,h)(r,c,h) 表示第 r rr 行第 c cc 列第 h hh 层，可能的走法有以下几种：

( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (1,3,1) − (1,6,1) − (3,6,1) − (5,6,1)(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) − (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) − (1,3,1) − (3,3,1) − (5,3,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) − (3,6,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) − (3,3,1) − (5,3,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,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) − (3,1,1) − (5,1,1) − (5,4,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,4,1) − (1,6,1) − (3,6,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) − (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) − (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 ) (1,1,1) − (3,1,1) − (5,1,1) − (5,6,1)(1,1,1)−(3,1,1)−(5,1,1)−(5,6,1)

数据范围

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

对于 60% 的评测用例， 1 ≤ n , m , w ≤ 300 。 1 ≤ n,m,w ≤ 300。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 1 ≤ n,m,w ≤ 1000，1 ≤ r 1 ,r 2 ≤ n, 1 ≤ c 1 ,c 2 ≤ m, 1 ≤ h 1 ,h 2 ≤ w1≤n,m,w≤1000，1≤r1,r2≤n,1≤c1,c2≤m,1≤h1,h2≤w，陷阱不在起点或终点，两个陷阱不同。