4435 - 三维迷宫

有一个立方体迷宫由若干长、宽、高均为1的小正立方体组成。

一个n行m列k层的立方体迷宫，现在需要从第1行第1列第1层的网格移动到第n行第m列第k层的网格。

在移动的过程中，每次移动只允许移动到行号+1或者列号+1或者层号+1的相邻小正立方体

另外有o个小正立方体它是障碍物，不允许停留、经过此小正立方体,保证起点(1,1,1)和终点(n,m,k)不是障碍物

求不同移动的方案数

第一行包含三个数字 n，m，k，o

接下来o行每行3个数字分别表示某个障碍物所在的行、列、层号

输出仅一个数字表示方案数，这个数字可能很大，你需要输出对10^9+7的模即可。

n,m,k \leq 40

原创