14038 - 三维迷宫

有一个立方体迷宫由若干长、宽、高均为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$ 的模即可。

三维迷宫