1731B.md (1899B)
1 Source: https://codeforces.com/problemset/problem/1731/B 2 3 B. Kill Demodogs 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 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. 26 27 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). 28 29 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! 30 31 (Note, you firstly multiply by $2022$ and only after that take the remainder.) 32 33 Input 34 35 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. 36 37 The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^9$) — the size of the grid. 38 39 Output 40 41 For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by $2022$, modulo $10^9 + 7$. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 2 51 52 3 53 54 50 55 56 1000000000 57 ``` 58 59 Output 60 61 ``` 62 14154 63 44484 64 171010650 65 999589541 66 ``` 67 68 Note 69 70 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$.