题目背景

一天，小 xi 看到了 mc 的一个地图,他立马下载来逝一下。

题目描述

这个迷宫有 d 种模式，每种模式的地图是由 $x_1 \times x_2 \times x_3 \times \ldots \times x_{d-1} \times x_d$ 个房间组成的，小 xi 初始在 $0,0,0 \ldots 0,0$ 号房间，终点在$x_1,x_2,x_3 \ldots x_{d-1}$，$x_d$ 号房间他每次可以从 $c_1,c_2,c_3 \ldots c_{d-1}$，$c_d$ 号房间走到$c_1+1,c_2,c_3 \ldots c_{d-1}$，$c_d$ 号房间或 $c_1$，$c_2+1,c_3 \ldots c_{d-1}$，$c_d$ 房间 $\ldots$ 或$c_1,c_2,c_3 \ldots c_{d-1}$，$c_d+1$ 房间，但在这些房间中，有 $n$ 个房间里有 $114514$ 个 creeepre 和 $1919810$个TNT，很明显，这些房间是不能走的。小xi想知道自己有多少种方法走到终点。

输入格式

第一行输入n,d。

第二行输入d个整数，分别为 $x_1,x_2,x_3 \ldots x_{d-1},x_d$。

第3到 $n+2$ 行每行输入 $d$ 个整数，分别为 $a_1,a_2,a_3 \ldots a_{d-1}, a_d$

输出格式

第一行输出有多少种方法到终点除以$10^9 + 7$的余数。

样例

样例输入

1 2
2 1
1 0

样例输出

1

解释说明

$n \leq 5$

$d \leq 4$

$x_i \leq 10^{17}$

$a_i \leq x_i$

测试点范围：

测试点1：$x_i \leq 10^{17},a_i \leq x_i,d=1$

测试点2：$x_i \leq 10^{17},a_i \leq x_i,d=1$

测试点3：$x_i \leq 10^{17},a_i \leq x_i,d=1$

测试点4：$x_i\leq 10^{17},a_i \leq x_i,d=1$

测试点5：$x_i \leq 1000,a_i \leq x_i,d=2$

测试点6：$x_i \leq 100,a_i \leq x_i,d=3$

测试点7：$x_i \le 100,a_i \leq x_i,d=3$

测试点8：$x_i \le 20,a_i \leq x_i,d=4$

测试点9：$x_i \le 20,a_i \leq x_i,d=4$

测试点10：$x_i \le 20,a_i \leq x_i,d=4$

链接：

分类讨论+标数法 (小奥-标数法)