Captain of Knights
Contest: 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 3100
Tags: math

Mr. Chanek just won the national chess tournament and got a huge chessboard of size $$$N \times M$$$. Bored with playing conventional chess, Mr. Chanek now defines a function $$$F(X, Y)$$$, which denotes the minimum number of moves to move a knight from square $$$(1, 1)$$$ to square $$$(X, Y)$$$. It turns out finding $$$F(X, Y)$$$ is too simple, so Mr. Chanek defines:

$$$G(X, Y) = \sum_{i=X}^{N} \sum_{j=Y}^{M} F(i, j)$$$

Given X and Y, you are tasked to find $$$G(X, Y)$$$.

A knight can move from square $$$(a, b)$$$ to square $$$(a', b')$$$ if and only if $$$|a - a'| > 0$$$, $$$|b - b'| > 0$$$, and $$$|a - a'| + |b - b'| = 3$$$. Of course, the knight cannot leave the chessboard.

Input format:
The first line contains an integer $$$T$$$ $$$(1 \le T \le 100)$$$, the number of test cases.

Each test case contains a line with four integers $$$X$$$ $$$Y$$$ $$$N$$$ $$$M$$$ $$$(3 \leq X \leq N \leq 10^9, 3 \leq Y \leq M \leq 10^9)$$$.

Output format:
For each test case, print a line with the value of $$$G(X, Y)$$$ modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
3 4 5 6
5 5 8 8

Example output:
27
70

Editorial:
An important observation is that it is guaranteed there is a sequence of moves from $$$(1, 1)$$$ to $$$(X, Y)$$$ where we only visit squares in the rectangle $$$(1, 1)$$$ to $$$(X, Y)$$$. So we can calculate $$$F(X, Y)$$$ independently without concerning $$$N$$$ dan $$$M$$$.
To ease the implementation and explanation, we define $$$\int(f(x)) = \sum_{i = 1}^{x}f(i)$$$. So the sum of an order two polynomial $$$F(x) = a \cdot x^2 + b \cdot x + c$$$ is $$$\int{F(x} = \frac{a}{3} x^3 + \frac{a + b}{2} x^2 + \frac{a + 3b + 6c}{6} x$$$
Since the number of formulas in this problem tutorial is quite large, we will omit the method to find it because then the editorial will be quite long Lets define $$$P(x,y) = \sum_{i = 3}^{x} \sum_{j = 3}^{y} F(i,j)$$$. If we can find $$$P(x, y)$$$ fast, the answer is $$$P(N,M) - P(X-1,M) - P(N,Y-1) + P(X-1,Y-1)$$$.
Calculating $$$P$$$ can be divided into three cases:
$$$\bullet$$$ Case 1, For $$$x = 3$$$, $$$y \le 5$$$. we can use brute force.
$$$\bullet$$$ Case 2,For $$$x < 2y$$$ and $$$y < 2x$$$. Let $$$z = (x + y - 2)$$$, $$$F(x, y) = s(z) = \frac{z}{3} + z \bmod 3$$$. Assume $$$t(x) = \int(s(x))$$$. For rows $$$i$$$ from 4 to $$$\frac{y}{2}$$$, the sum of $$$F$$$ is $$$t(3(i-1)) - t(\frac{3i}{2}-2)$$$. For rows $$$i$$$ greater than $$$\frac{y}{2}$$$ next rows, the sum of $$$F$$$ is $$$t(i+y-2) - t(\frac{3i}{2}-2)$$$. To ease in finding the sum, we define:
• $$$a(x) = t(1) + t(2) + ... + t(x)$$$
• $$$b(x) = t(3) + t(6) + ... + t(3x)$$$
• $$$c(x) = t(1) + t(2) + t(4) + t(5) + ... + t(\frac{3x-1}{2})$$$
• $$$t(3x) = \int(3x+1)$$$,
• $$$a(3x) = \int(3 \int(3x+1) - (3x+1))$$$
• $$$b(x) = \int(\int(3x+1))$$$
• $$$c(2x) = a(3x) - b(x)$$$.
$$$\bullet$$$ Case 3, for $$$2y \le 2 \cdot x$$$ or $$$x \le 2 \cdot y$$$. First see the illustration below for context.
The sum of $$$F(x, y)$$$ for each blocks of two columns starting at an even number is the same. We define $$$blocks$$$ as these columns. So, block $$$1$$$ is the $$$[3, 4]$$$ block, block $$$2$$$ is the $$$[5, 4]$$$ block, and so on. The sum of a row in block $$$i$$$ is $$$(2 \cdot x + 5)$$$. Since there are $$$i$$$ rows in block $$$i$$$, the sum of all rows in block $$$i$$$ is $$$i(2 \cdot i + 5)$$$. To ease, lets define two functions:
1. $$$d(x) = \int{x (2 \cdot x + 5)}$$$. Sum of all $$$F$$$ for the first $$$x$$$ blocks.
2. $$$e(x) = \int{(2 \cdot x + 5 )}$$$. Sum of a row for the first $$$x$$$ blocks.
The sum of this part is divided into three regions which is also described in the image above (red, yellow, green).
1. the sum on the green area is $$$d(N-1)$$$.
2. There is a square of height $$$N$$$ from colums $$$N-1$$$ to $$$\frac{M}{2}$$$. So, the sum of this region is $$$N(e(\frac{M}{2})-e(N-1))$$$
3. The red area. This is a single row at the end if $$$M$$$ is odd. If $$$N$$$ is even, the sum is $$$\frac{N}{2} \cdot (M + 6)$$$. If N is odd, we add an additional square which is $$$F(N + 2, M + 5)$$$ (remember we simplify $$$N$$$ and $$$M$$$ at the beginning.
So, the sum of case three is $$$d(N-1) + N(e(\frac{M}{2})-e(N-1)) $$$ + red area. Calculate this formula again with the rows swapped to for case $$$y \ge 2 \cdot x$$$.
note: Calculating $$$t(x)$$$ and $$$a(x)$$$ when $$$x$$$ is not a multiple of $$$3$$$ can be done by finding the closest multiple of $$$3$$$ and then bruteforcing the last columns. That can also be used to calculate $$$c(x)$$$ and $$$e(x)$$$ when $$$x$$$ is odd.
Time Complexity: $$$O(T)$$$