A grid of size (2n + 1) × (2n + 1) has been constructed as follows. Number 1 has been placed in the center square, number 2 has been placed to the right of it, and the following numbers have been placed along the spiral counterclockwise.</p>

Your task is to calculate answers for q queries where the sum of numbers in an rectangular region in the grid is requested (modulo 10⁹ + 7). For example, in the following grid n = 2 and the sum of numbers in the gray region is 74:

입력 형식

The first input line contains two integers n and q: the size of the grid and the number of queries.</p>

After this, there are q lines, each containing four integers x₁, y₁, x₂ and y₂ (-n ≤ x₁ ≤ x₂ ≤ n, -n ≤ y₁ ≤ y₂ ≤ n). This means that you should calculate the sum of numbers in a rectangular region with corners (x₁, y₁) and (x₂, y₂).

출력 형식

You should output the answer for each query (modulo 10⁹ + 7).

예제 입력

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

예제 출력

74
9
14