Pretty Table
시간 제한1초메모리 제한512 MB
중앙에서 시작하는 N×N 시계 방향 나선 격자에서 (R1,C1)부터 (R2,C2)까지 부분 격자의 합을 1,000,000,007로 나눈 나머지를 구한다.
문제
A pretty table is a grid with N rows and N columns containing integers from 1 to N2. The numbers are written on the grid following these rules:
- At first, 1 is written in the center cell, i.e. the cell on the (N/2+1)-th row and ((N/2+1)-th column, where / is the integer division (i.e. rounded down since N/2 here is always positive).
- Then, starting from the cell on the left of the cell containing integer 1, in clockwise direction, continues writing the integers 2 to N2 one by one, surrounding the existing numbers.
For example, if N = 5, the table will look like this:
Given N, R1, R2, C1, and C2, calculates the sum of the integers contained within the sub-grid having (R1, C1) and (R2, C2) as the top-left-most cell and the bottom-right-most cell. Note that the table index starts from 1 to N on both row and column.
입력
The input contains five integers in a line: N R1 R2 C1 C2 (1 ≤ N ≤ 1,000,000,000; 1 ≤ R1 ≤ R2 ≤ N; 1 ≤ C1 ≤ C2 ≤ N) as stated in the problem description.
출력
The output contains the remainder of the answer when divided by 1,000,000,007, in a line.