Processing math: 100%
编程题
                质数行者

题目描述

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

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

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

在游戏中有两个陷阱,分别为第 r1 行第 c1 列第 h1 层和第 r2 行第 c2 列第 h2 层。这两个陷阱的位置可以跨过,但不能停留。也就是说,小蓝不能控制角色某一步正好走到陷阱上,但是某一步中间跨过了陷阱是允许的。

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

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

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

输入描述

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

第二行包含 6 个整数,r1,c1,h1,r2,c2,h2,表示陷阱的位置。

其中有 ,1n,m,w10001r1,r2n,1c1,c2m,1h1,h2w,陷阱不在起点或终点,两个陷阱不同。

输出描述

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

输入输出样例

示例

>输入

5 6 1
3 4 1 1 2 1

>输出

11
查看答案
赣ICP备20007335号-2