一个大小为 $(2n + 1) \times (2n + 1)$ 的网格构造如下：数字 $1$ 被放置在中心方格中，数字 $2$ 被放置在它的右侧，随后的数字按逆时针方向沿螺旋放置。

你的任务是计算 $q$ 个查询的答案，每个查询要求计算网格中一个矩形区域内数字的和（模 $10^9 + 7$）。例如，在下方的网格中，$n = 2$，灰色区域内数字的和为 $74$：

输入格式

第一行包含两个整数 $n$ 和 $q$：网格的大小和查询的数量。

此后有 $q$ 行，每行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$（$-n \le x_1 \le x_2 \le n, -n \le y_1 \le y_2 \le n$）。这意味着你需要计算以 $(x_1, y_1)$ 和 $(x_2, y_2)$ 为顶点的矩形区域内数字的和。

输出格式

你需要输出每个查询的答案（模 $10^9 + 7$）。

样例

输入 1

2 3
0 -2 1 1
-1 0 1 0
1 2 1 2

输出 1

74
9
14

子任务

在所有子任务中，$1 \le q \le 100$。

• 子任务 1（12 分）：$1 \le n \le 1000$
• 子任务 2（15 分）：$1 \le n \le 10^9$，$x_1 = x_2$ 且 $y_1 = y_2$
• 子任务 3（17 分）：$1 \le n \le 10^5$
• 子任务 4（31 分）：$1 \le n \le 10^9$，$x_1 = y_1 = 1$
• 子任务 5（25 分）：$1 \le n \le 10^9$