你想要在 $n$ 维空间中从 $(0, 0, \dots, 0)$ 走到 $(a_0, a_1, \dots, a_{n-1})$。在每一步中，你可以将坐标向量的一个分量增加 1。空间中存在 $m$ 个障碍物 $p_1, p_2, \dots, p_m$。你需要求出不经过这些障碍物的路径数量。

然而，对于 8102 年的 ICPC 比赛来说，这个问题太简单了。我们增加了一个额外的约束：对于路径上的每一个点 $(x_0, x_1, \dots, x_{n-1})$，其坐标向量的分量必须满足非递减条件：$x_0 \le x_1 \le \dots \le x_{n-1}$。

输出路径数量对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50, 0 \le m \le 50$)。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_0 \le a_1 \le \dots \le a_{n-1} \le 10^4$)，即终点的坐标向量。

接下来的 $m$ 行描述障碍物。第 $i$ 行包含 $n$ 个整数 $p_{i,0}, p_{i,1}, \dots, p_{i,n-1}$ ($0 \le p_{i,0} \le p_{i,1} \le \dots \le p_{i,n-1} \le 10^4$)，即一个障碍物的坐标向量。

起点、终点以及所有障碍物互不相同。

输出格式

输出答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

2 0
3 3

输出 1

5

输入 2

4 2
1 2 3 4
0 1 2 3
1 1 2 2

输出 2

312