Kill Demodogs
Contest: Codeforces Round 841 (Div. 2) and Divide by Zero 2022
Difficulty rating: 1100
Tags: greedy, math

Demodogs from the Upside-down have attacked Hawkins again. El wants to reach Mike and also kill as many Demodogs in the way as possible.

Hawkins can be represented as an $$$n \times n$$$ grid. The number of Demodogs in a cell at the $$$i$$$-th row and the $$$j$$$-th column is $$$i \cdot j$$$. El is at position $$$(1, 1)$$$ of the grid, and she has to reach $$$(n, n)$$$ where she can find Mike.

The only directions she can move are the right (from $$$(i, j)$$$ to $$$(i, j + 1)$$$) and the down (from $$$(i, j)$$$ to $$$(i + 1, j)$$$). She can't go out of the grid, as there are doors to the Upside-down at the boundaries.

Calculate the maximum possible number of Demodogs $$$\mathrm{ans}$$$ she can kill on the way, considering that she kills all Demodogs in cells she visits (including starting and finishing cells).

Print $$$2022 \cdot \mathrm{ans}$$$ modulo $$$10^9 + 7$$$. Modulo $$$10^9 + 7$$$ because the result can be too large and multiplied by $$$2022$$$ because we are never gonna see it again!

(Note, you firstly multiply by $$$2022$$$ and only after that take the remainder.)

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — the size of the grid.

Output format:
For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by $$$2022$$$, modulo $$$10^9 + 7$$$.

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

Note:
In the first test case, for any path chosen by her the number of Demodogs to be killed would be $$$7$$$, so the answer would be $$$2022 \cdot 7 = 14154$$$.

Example input:
4
2
3
50
1000000000

Example output:
14154
44484
171010650
999589541

Editorial:
To kill the maximum number of demodogs, El can travel in zigzag fashion, i.e. from $$$(1,1)$$$ to $$$(1,2)$$$ to $$$(2,2)$$$ and so on. Thus the answer would be the sum of elements at $$$(1,1)$$$, $$$(1,2)$$$, $$$(2,2)$$$ $$$\dots$$$ $$$(n,n)$$$. i.e. the answer is $$$$$$\sum_{i = 1}^n{i \cdot i} + \sum_{i = 1}^{n-1}{i (i + 1)} = \frac{n(n + 1)(4n - 1)}{6}$$$$$$.
And the answer you need to print is $$$$$$2022 \frac{n(n + 1)(4n - 1)}{6} = 337 \cdot n(n + 1)(4n - 1) \pmod{10^9 + 7}$$$$$$
Proof:
Let $$$kills_{i,j}$$$ be the maximum number of kills of all possible paths from $$$(1,1)$$$ to $$$(i,j)$$$.
$$$kills_{n-1,n-1} \geq kills_{i,n - 1}$$$ + number of demodogs from $$$(i + 1,n - 1)$$$ to $$$(n - 1,n - 1)$$$ $$$( \forall i \hspace{1.5mm} \in \hspace{1.5mm} [1, n - 2])$$$.
$$$$$$kills_{n-1,n-1} \geq kills_{i,n - 1} + \sum_{j = i + 1}^{n - 1}{j \cdot (n - 1)}$$$$$$
$$$$$$kills_{n-1,n-1} \geq kills_{i,n - 1} + \frac{(n - 1 - i)((i + 1)(n - 1) + (n - 2 - i)(n - 1))}{2} \text{ (sum of A.P.)}$$$$$$
$$$$$$kills_{n-1,n-1} \geq kills_{i,n - 1} + \frac{(n - 1 - i)(n - 1)^2}{2} \text{ (1)}$$$$$$
Let $$$killsZ$$$ be the number of kills if El travels in zigzag fashion, i.e. she goes to $$$(n,n)$$$ after passing through $$$(n - 1,n - 1)$$$: $$$$$$killsZ_{n,n} = kills_{n - 1,n - 1} + n(n - 1) + n \cdot n$$$$$$
Let $$$killsNZ$$$ be the maximum number of kills If El goes to $$$(n,n)$$$ after passing through $$$(i,n)$$$ for some $$$i$$$ in range of $$$[1 \dots n - 1]$$$, i.e. El goes from $$$(1,1)$$$ to $$$(i,n - 1)$$$ to $$$(i,n)$$$ to $$$(n,n)$$$: $$$$$$killsNZ_{n,n} = kills_{i,n - 1} + \text{no of demigods from } (i,n)\text{ to }(n,n)$$$$$$
$$$$$$killsNZ_{n,n} = kills_{i,n - 1} + \sum_{j = i}^{n}{j \cdot n}$$$$$$
$$$$$$killsNZ_{n,n} = kills_{i,n - 1} + \frac{(n + 1 - i)(n + i)n}{2}$$$$$$
$$$$$$killsZ_{n,n} - killsNZ_{n,n} = kills_{n - 1,n - 1} + n(n - 1) + n \cdot n - kills_{i,n - 1} - \frac{(n + 1 - i)(n + i)n}{2} \text{ from $(1)$}$$$$$$
$$$$$$killsZ_{n,n} - killsNZ_{n,n} \geq kills_{i,n - 1} + \frac{(n - 1 - i)(n - 1)^2}{2} + n(n - 1) + n \cdot n - kills_{i,n - 1} - \frac{(n + 1 - i)(n + i)n}{2}$$$$$$
$$$$$$killsZ_{n,n} - killsNZ_{n,n} \geq \frac{2 n^2 - 3 n - n \cdot i - i - 1}{2}$$$$$$
$$$$$$killsZ_{n,n} - killsNZ_{n,n} \geq 0$$$$$$ since $$$2n^2 - 3 n - n \cdot i - i - 1 \geq 0$$$ for all $$$i \in \hspace{1.5mm} [1, n - 2]$$$.
In other words, $$$killsZ_{n,n} \geq killsNZ_{n,n}$$$ Therefore zigzag path guarantees maximum number of demodog kills.
Now, the last thing was taking the modulus. Modulus should always be taken after every multiply operation to avoid the overflow. You can refer to modular arithmetic for more details.
And the main reason we told you to multiply the answer by $$$2022$$$ is that we needed to divide it by $$$6$$$. For division, we have to take inverse modulo in modular arithmetic. So, in order to avoid that, we gave you a multiple of $$$6$$$, which is $$$2022$$$.