T294468 提高 T2 - 波特

有一个 $6\times n$ 的网格，第 $i$ 行第 $j$ 列的格子记为 $(i,j)\ (i\in [1,6],\ j\in [1,n])$。 波特需要从第一列的任意格子移动到最后一列的任意格子，但是有如下要求： 1. 每一秒，波特可以向右上、正右、右下这三个方向移动到下一列的格子上。也就是说处在 $(i,j)$ 的波特下一秒可能的位置是 $(i-1,j+1),(i,j+1),(i+1,j+1)$，当然任何时候波特都必须在网格内。 2. 网格中有 $m$ 个障碍，每一块障碍的形状都是一个矩形，任何时刻波特的位置都不能在障碍上。注意障碍可能重叠。 现在你要求出，波特从第一列的任意一个格子出发，走到最后一列的任意一个格子，有多少种走法？由于答案很大，所以需要对 $10^9+7$ 取模。 两种走法不同，当且仅当波特经过的格子集合不相等。

第一行：两个整数 $n,m$。 接下来 $m$ 行：每行四个整数 $x_1,y_1,x_2,y_2$，表示有一个左上角在 $(x_1,y_1)$，右下角在 $(x_2,y_2)$ 的矩形障碍。

第一行：一个整数，表示答案对 $10^9+7$ 取模。

【样例 1 解释】 从 $(1,1)$ 出发，可以到达 $(1,2)$ 和 $(2,2)$ 共 $2$ 个点； 从 $(i,1)\ \ (2\leq i\leq 5)$ 出发，可以到达 $(i-1,2),\ \ (i,2)$ 和 $(i+1,2)$ 共 $3$ 个点； 从 $(6,1)$ 出发，可以到达 $(5,2)$ 和 $(6,2)$ 共 $2$ 个点。 所以总走法是 $2+3\times 4+2=16$。 【数据范围】 对于 $100\%$ 的数据：$2\leq n\leq 10^{18},\ 0\leq m\leq 10^3,\ 1\leq x_1\leq x_2\leq 6,\ 2\leq y_1\leq y_2\leq n​-1$。 | 子任务编号 | $n\leq$ | $m\leq $ | 特殊性质 | 分值 | | :----------: | :-------: | :------: | :------: | :---: | | Subtask 1 | $10^5$ | $0$ | 无 | 10 | | Subtask 2 | $10^5$ | $10^3$ | 有 | 10 | | Subtask 3 | $10^5$ | $10^3$ | 无 | 20 | | Subtask 4 | $10^{18}$ | $0$ | 无 | 20 | | Subtask 5 | $10^{18}$ | $10^3$ | 有 | 20 | | Subtask 6 | $10^{18}$ | $10^3$ | 无 | 20 | 特殊性质：对于所有障碍，$x_1=x_2,\ \ y_1=y_2$，即每个障碍只占据一格。