B. Kill Demodogstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputDemodogs 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.)InputEach 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.OutputFor each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by 2022, modulo 10^9 + 7.ExampleInput
423501000000000Output
14154
44484
171010650
999589541
NoteIn 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.
423501000000000
14154 44484 171010650 999589541 
['greedy', 'math', '*1100']