나선 격자의 직사각형 합

문제

크기가 $(2n+1) \times (2n+1)$ 인 격자를 다음과 같이 채운다. 가운데 칸에 $1$ 을 적고, 그 오른쪽 칸에 $2$ 를 적은 다음, 반시계 방향으로 나선을 그리며 이어지는 수를 차례로 적는다.

칸의 위치는 정수 좌표 $(x, y)$ 로 나타낸다. 가운데 칸이 $(0, 0)$ 이고, $x$ 는 오른쪽으로 갈수록 커지며 $y$ 는 위로 갈수록 커진다. 그래서 격자의 모든 칸은 $-n \le x \le n$ 과 $-n \le y \le n$ 을 만족한다. $n = 2$ 인 격자는 이렇게 채워진다.

	$x=-2$	$x=-1$	$x=0$	$x=1$	$x=2$
$y=2$	17	16	15	14	13
$y=1$	18	5	4	3	12
$y=0$	19	6	1	2	11
$y=-1$	20	7	8	9	10
$y=-2$	21	22	23	24	25

직사각형 영역 $q$ 개가 주어진다. 각 영역에 들어 있는 수의 합을 $10^9+7$ 로 나눈 나머지를 구하라.

입력

첫째 줄에 격자의 크기 $n$ 과 질의의 개수 $q$ 가 주어진다.

이어지는 $q$ 개 줄에 각각 네 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 주어진다. 이는 두 꼭짓점 $(x_1, y_1)$ 과 $(x_2, y_2)$ 가 정하는 직사각형 영역, 즉 $x_1 \le x \le x_2$ 와 $y_1 \le y \le y_2$ 를 만족하는 칸 전체를 뜻한다.

출력

질의마다 한 줄에 그 영역에 들어 있는 수의 합을 $10^9+7$ 로 나눈 나머지를 출력한다.

제한

$1 \le n \le 10^9$
$1 \le q \le 100$
$-n \le x_1 \le x_2 \le n$
$-n \le y_1 \le y_2 \le n$