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-----

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-----

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


-----Examples-----

Input
4
2
3
50
1000000000
Output
14154
44484
171010650
999589541


-----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$.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
readline = sys.stdin.readline
T = int(readline())
mod = 1000000007
direction = [(0, 1), (1, 0)]
for _ in range(T):
	N = int(readline())
	one = 1
	two = N * (N + 1) * (2 * N + 1) // 6
	three = N * (N + 1) // 2
	answer = one + 2 * (two - 1) - (three - 1)
	answer *= 2022
	answer %= mod
	print(answer)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = n * (n + 1) * (4 * n - 1) // 6
	print(s * 2022 % (10 ** 9 + 7))


mod = 10 ** 9 + 7
for n in [*open(0)][1:]:
	n = int(n)
	x = n * (n + 1) * (2 * n + 1) // 3
	x -= n + n * (n - 1) // 2
	print(x * 2022 % mod)


import sys
input = sys.stdin.readline
mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	N = int(input())
	ans = N * (N + 1) * (2 * N + 1) // 3 - N * (N + 1) // 2
	ans *= 2022
	ans %= mod
	print(ans)


for i in [*open(0)][1:]:
	i = int(i)
	print((i * (i + 1) * (2 * i + 1) // 3 - i * (i + 1) // 2) * 2022 % (10 ** 9 + 7))


for i in [*open(0)][1:]:
	i = int(i)
	print((i + 1) * (4 * i * i - i) * 337 % (10 ** 9 + 7))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
num_test = inp()
for test_idx in range(num_test):
	n = inp()
	a = n * (n + 1) * (2 * n + 1)
	b = n * (n + 1)
	c = a // 3 - b // 2
	ans = 2022 * c % (10 ** 9 + 7)
	print(ans)


def kill(n):
	return n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2
t = int(input())
r = []
for i in range(0, t):
	n = int(input())
	r.append(kill(n) * 2022 % (10 ** 9 + 7))
for i in r:
	print(i)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	ans = n * (4 * n * n + 3 * n - 1) // 6
	ans = ans * 2022 % 1000000007
	print(ans)


import sys

def in_int():
	return int(sys.stdin.readline())

def in_str():
	return sys.stdin.readline().rstrip()

def in_map_int():
	return map(int, sys.stdin.readline().split())

def in_arr_int():
	return list(map(int, sys.stdin.readline().split()))

def in_arr_str():
	return sys.stdin.readline().split()

def is_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return True
	return False

def bin2dec(s):
	n = 0
	for i in range(len(s)):
		n += int(s[len(s) - i - 1]) * 2 ** i
	return n

def dec2bin(n):
	if n == 0:
		return '0'
	ans = ''
	while n > 0:
		ans += str(n % 2)
		n //= 2
	return ans[::-1]

def solve(n):
	a = n * (n + 1) * (2 * n + 1) // 6
	b = n * (n - 1) * (2 * n - 1) // 6
	c = n * (n - 1) // 2
	return 2022 * (a + b + c) % (1000000000 + 7)

def main():
	t = in_int()
	for _ in range(t):
		n = in_int()
		print(solve(n))
main()


mod = 10 ** 9 + 7
for n in [*open(0)][1:]:
	n = int(n)
	ans = n * (n ** 2 - 1) // 3
	ans += n * (n + 1) * (2 * n + 1) // 6
	print(ans * 2022 % mod)


import sys
t = int(sys.stdin.readline())
p = 10 ** 9 + 7
for i in range(t):
	n = int(sys.stdin.readline())
	a = 674 * n * (n - 1) * (2 * n - 1) % p
	b = 1011 * n * (n - 1) % p
	c = 2022 * n * n % p
	ans = (a + b + c) % p
	sys.stdout.write(str(ans) + '\n')


t = int(input())
sizes = [None] * t
for i in range(t):
	sizes[i] = int(input())
for i in range(t):
	n = sizes[i]
	if n <= 1000000000:
		print(int(n * (n + 1) * (4 * n - 1) * 2022 // 6 % 1000000007))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	a = int(input())
	print(2022 * (a * (a + 1) * (4 * a - 1) // 6) % (10 ** 9 + 7))


s = int(input())
arr = []
for _ in range(s):
	h = int(input())
	arr.append(h)
for n in arr:
	m = 10 ** 9 + 7
	ans = n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2
	print(int(int(ans * 2022 % m)))


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	ans = n * (4 * n * n + 3 * n - 1) // 6
	print(ans * 2022 % (10 ** 9 + 7))


import sys
import math
input = sys.stdin.readline
T = int(input())
for i in range(T):
	N = int(input())
	res = N * (N + 1) * (2 * N + 1) // 3 - N * (N + 1) // 2
	res *= 2022
	res %= 1000000007
	print(res)


ans = list()
for i in range(int(input())):
	n = int(input())
	s = n * (4 * n ** 2 + 3 * n - 1) * 337 % (10 ** 9 + 7)
	ans.append(int(s))
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	res = int(4 * n * n * n + 3 * n * n - n) // 6 * 2022 % int(10 ** 9 + 7)
	print(int(res))


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def formula(n):
	s = n * (n + 1) * (2 * n + 1) // 3 + n * (n + 1) // 2
	return s

def solve():
	n = inp()
	s = formula(n - 1)
	s = s + n * n
	print(s * 2022 % 1000000007)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


t = int(input(''))
A = []
for i in range(t):
	n = int(input(''))
	A.append(n)
for i in range(t):
	n = A[i]
	bruh = 337 * (n * (n + 1) * (4 * n - 1))
	print(bruh % 1000000007)


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	m = 10 ** 9 + 7
	ans = n * (n + 1) * (2 * n + 1) // 3 + n * (n + 1) // 2 - n * (n + 1)
	return 2022 * ans % m
for _ in range(int(input())):
	print(solve())


t = int(input())
a = []
for i in range(t):
	n = int(input())
	ans = n * (n + 1) * (4 * n - 1) * 337
	ans = ans % (10 ** 9 + 7)
	a.append(ans)
for i in range(t):
	print(a[i])


modulo = 10 ** 9 + 7
t = int(input())
B = []
for i in range(t):
	n = int(input())
	m = n - 1
	suma = n * (n + 1) * (2 * n + 1) // 6 + m * (m + 1) * (m + 2) // 3
	B.append(suma * 2022)
for i in B:
	print(i % modulo)


tc = int(input())
mod = 1000000007
list = []
while tc > 0:
	n = int(input())
	n2 = n * n
	n3 = n * n * n
	ans = 4 * n3 + 3 * n2 - n
	ans = ans * 337 % mod
	list.append(ans)
	tc -= 1
for i in list:
	print(i)


import heapq
import sys
import math
import itertools
import os
input = lambda : sys.stdin.readline().strip()

def solve():
	mod = 7 + 10 ** 9
	n = int(input())
	tot = 2 * (n * (n + 1) * (2 * n + 1) // 6) + n * (n + 1) // 2 - n * n - n
	tot = tot * 2022 % mod
	print(tot)
for i in range(int(input())):
	solve()


from decimal import Decimal
result = []
for i in range(int(input())):
	n = int(input())
	d1 = n * (n + 1) * (2 * n + 1) // 6
	res1 = d1 + (d1 - n * (n + 1) // 2)
	res2 = n * (n + 1) // 2 + n * n * (n + 1) // 2 - n
	res = max(res1, res2)
	result.append(Decimal(res * 2022) % 1000000007)
for i in result:
	print(int(i))


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	print(n * (n + 1) * (4 * n - 1) // 6 * 2022 % m)


t = int(input())
mod = 1000000007
for i in range(t):
	n = int(input())
	ans = n * (n + 1) * (4 * n - 1) // 6
	ans *= 2022
	ans %= mod
	print(ans)


t = int(input())
num = 1000000007
for i in range(0, t):
	n = int(input())
	y = (674 * n * (n + 1) * (2 * n + 1) - 1011 * n * (n + 1)) % num
	print(y)


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	print(337 * (n * (n + 1) * (4 * n - 1)) % mod)


for i in range(int(input())):
	n = int(input())
	print(337 * n * (n + 1) * (4 * n - 1) % (10 ** 9 + 7))


for i in range(int(input())):
	n = int(input())
	print(n * (n + 1) * (4 * n - 1) // 6 * 2022 % (10 ** 9 + 7))


for i in range(int(input())):
	n = int(input())
	print(n * (n + 1) * (4 * n - 1) // 6 * 2022 % 1000000007)


t = int(input())
m = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	ans = 2022 * (n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2) % m
	print(ans)


for _ in range(int(input())):
	k = 10 ** 9 + 7
	n = int(input())
	total = 1
	j = (n + 1) * n * (2 * n + 1) // 3
	k = (n + 1) * n // 2
	t = (j - k) * 2022
	t = t % (10 ** 9 + 7)
	print(t)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	print(337 * n * (n + 1) * (4 * n - 1) % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = n * (n + 1) * (2 * n + 1) // 6
	s2 = n * (n + 1) // 2
	print((2 * s1 - s2) * 2022 % 1000000007)


t = int(input())
while t > 0:
	n = int(input())
	s = n * (n + 1) * (4 * n - 1) // 6
	s = s * 2022
	s = s % 1000000007
	print(s)
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	ans = n * (n + 1) * (4 * n - 1) * 337
	ans %= 1000000007
	print(ans)


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	print((n * (n + 1) * (4 * n + 5) // 6 - n ** 2 - n) * 2022 % mod)


t = int(input())
for _ in range(t):
	n = int(input())
	print((4 * n * n * n + 3 * n * n - n) // 6 * 2022 % 1000000007)


t = int(input())

def fun(x):
	return x * (x + 1) * (2 * x + 1) // 6
for i in range(t):
	n = int(input())
	ans = fun(n) + fun(n - 1) + (n - 1) * n // 2
	ans *= 2022
	ans %= 1000000007
	print(ans)


def merge(a, b):
	global cnt
	i = 0
	j = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] <= b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			cnt += len(a) - i
			j += 1
	if i == len(a):
		for k in range(j, len(b)):
			ans.append(b[k])
	else:
		for k in range(i, len(a)):
			ans.append(a[k])
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	ans = n * (n + 1) * (4 * n - 1) // 6
	ans *= 2022
	ans %= 1000000007
	print(ans)


MOD = 1000000007

def ris(n):
	return n * (n + 1) * (2 * n + 1) * 674 - n * (n + 1) * 1011
T = int(input())
for t in range(T):
	print(ris(int(input())) % MOD)


t = int(input())
MOD = int(1000000000.0 + 7)
for _ in range(t):
	n = int(input())
	ans = 2022 * (n * (n - 1) * (2 * n - 1) // 3 + n * (n - 1) // 2 + n ** 2) % MOD
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	ans = n * (n - 1) * (n + 1) // 3 + n * (2 * n + 1) * (n + 1) // 6
	print(int(ans * 2022 % int(1000000000.0 + 7)))


mod = 10 ** 9 + 7

def solve():
	n = int(input())
	a = n
	b = n + 1
	c = 4 * n - 1
	if a % 6 == 0:
		a //= 6
		print(a * b * c * 2022 % mod)
		return
	if b % 6 == 0:
		b //= 6
		print(a * b * c * 2022 % mod)
		return
	if c % 6 == 0:
		c //= 6
		print(a * b * c * 2022 % mod)
		return
	if a % 2 == 0:
		a //= 2
		if b % 3 == 0:
			b //= 3
		elif c % 3 == 0:
			c //= 3
	elif b % 2 == 0:
		b //= 2
		if a % 3 == 0:
			a //= 3
		elif c % 3 == 0:
			c //= 3
	elif c % 2 == 0:
		c //= 2
		if a % 3 == 0:
			a //= 3
		elif b % 3 == 0:
			b //= 3
	print(a * b * c * 2022 % mod)
t = int(input())
for i in range(t):
	solve()


mod = int(1000000000.0 + 7)
T = int(input())
for _ in range(T):
	n = int(input())
	result = 2022 * (n * (n + 1) * (4 * n - 1)) // 6 % mod
	print(result)


for _ in range(int(input())):
	n = int(input())
	ans = n * (n + 1) * (2 * n + 1) // 6
	n -= 1
	ans += n * (n + 1) * (n + 2) // 3
	print(ans * 2022 % 1000000007)


for i in range(int(input())):
	n = int(input())
	res = 0
	M = 1000000007
	res = n * (n + 1) * (4 * n - 1) // 6
	res = res * 2022
	print(res % M)


def updown(gridno):
	ans = 0
	ans = gridno * (gridno + 1) * (2 * gridno + 1) // 3 - gridno * (gridno + 1) // 2
	return ans * 2022
cons = 10 ** 9 + 7
for i in range(int(input())):
	print(updown(int(input())) % cons)


import sys
import math
MOD = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	ans = n * (n + 1) * (4 * n - 1) // 6
	ans *= 2022
	ans %= MOD
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = n * (n + 1) * (2 * n + 1) // 6
	ans = a + a - (n + n * n) // 2
	print(ans * 2022 % 1000000007)


for i in range(int(input())):
	n = int(input())
	ans = n * (n + 1) * (4 * n - 1) * 337
	ans = ans % 1000000007
	print(ans)


t = int(input())
while t >= 1:
	t -= 1
	n = int(input())
	res = (n + 1) * (4 * n * n - n) // 6
	res *= 2022
	res %= 1000000007
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	ans = (n - 1) * (2 * n - 1) * n // 3 + n * (n - 1) // 2 + n * n
	ans *= 2022
	ans %= 1000000007
	if ans < 0:
		ans = 1000000007 + ans
	print(ans)


for _ in range(int(input())):
	n = int(input())
	mx = 0
	sm = 2022
	sm *= n * (n + 1)
	sm *= 4 * n - 1
	sm //= 6
	sm %= 10 ** 9 + 7
	print(sm)
	continue
	z = n - 1
	sm = z * (z + 1) // 2
	sm -= n - 1
	xx = z * n
	sm2 = n * (z + xx) // 2
	ans = sm + sm2 + n * n
	ans = 2022 * ans
	mx = max(ans, mx)
	z = 2 * n
	sm1 = n * (2 + z) // 2
	z2 = n
	z3 = n * n
	sm2 = n * (z2 + z3) // 2 - n - n * 2
	ans = sm1 + sm2 + 1
	ans = 2022 * ans
	mx = max(ans, mx)
	print(mx % (10 ** 9 + 7))
	s1 = n * (n + 1) // 2
	zz = n
	zzz = n * n
	s2 = n * (z + zzz) // 2
	ans = s1 + s2 - n
	ans = ans * 2022
	mx = max(ans, mx)
	print(mx % (10 ** 9 + 7))


mod = 10 ** 9 + 7
for tc in range(int(input())):
	n = int(input())
	x = n * (n + 1) * (4 * n - 1)
	x = x // 6
	x = x * 2022 % mod
	print(x)


MODULO = 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	ans = n * (n + 1) * (2 * n + 1) // 3 - 1
	ans -= n * (n + 1) // 2 - 1
	print(2022 * ans % MODULO)


t = int(input())
for i in range(t):
	n = int(input())
	mod = 1000000007
	print(n * (n + 1) * (4 * n - 1) * 337 % mod)


def solve():
	md = int(1000000000.0 + 7)
	n = int(input())
	count = n * (n - 1) * (n + 1) // 3
	sum = count + n * (n + 1) * (2 * n + 1) // 6
	print(2022 * sum % md)
t = int(input())
while t > 0:
	solve()
	t -= 1


for i in range(int(input())):
	n = int(input())
	ans = (4 * n ** 3 + 3 * n ** 2 - n) * 2022 // 6
	print(ans % 1000000007)


n = int(input())
for i in range(n):
	a = int(input())
	val = (a - 1) * a * (2 * a - 1) // 3 + a * (a - 1) // 2 + a * a
	print(val * 2022 % 1000000007)


t = int(input(''))
while t > 0:
	n = int(input(''))
	ans = (4 * n * n * n + 3 * n * n - n) * 337
	ans = ans % 1000000007
	print(ans)
	t -= 1


for t in range(int(input())):
	N = int(input())
	RMOD = int(1000000000.0 + 7)
	res = 2 * (N * (N + 1) * (2 * N + 1)) // 6
	res -= N * (N + 1) // 2
	res *= 2022
	print(res % RMOD)


t = int(input())
for i in range(t):
	n = int(input())
	print(f'{n * (n + 1) * (4 * n - 1) * 337 % 1000000007:.0f}')


t = int(input())
for i in range(t):
	n = int(input())
	a = n
	b = n + 1
	c = 4 * n - 1
	ele = a * b * c * 337 % 1000000007
	print(ele)


t = int(input())
for i in range(t):
	n = int(input())
	print((n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2) * 2022 % 1000000007)


t = int(input())
for i in range(t):
	n = int(input())
	su = 0
	su = n * (n + 1) * (4 * n + 5) // 6
	su = su - n * (n + 1)
	print(su * 2022 % (10 ** 9 + 7))


def cases():
	n = int(input())
	mod = 1000000000 + 7
	(a, b) = (1, 1)
	a = n * (n + 1) // 2 * (2 * n + 1) // 3 % mod
	b = n * (n - 1) * (n + 1) // 3 % mod
	print((a + b) * 2022 % mod)
	return
T = int(input())
for _ in range(T):
	cases()


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	mod = 1000000007
	ans = n * (n + 1) * (4 * n + 5) // 6 - (n * n + n)
	ans = ans * 2022 % mod
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	mod = 10 ** 9 + 7
	res = n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2
	print(res * 2022 % mod)


for _ in range(int(input())):
	n = int(input())
	num = (n + 1) * (2 * n * (n - 1) + n * (2 * n + 1)) // 6
	print(num * 2022 % 1000000007)


c = int(input())
for _ in range(c):
	n = int(input())
	res = n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2
	print(int(res * 2022 % (10 ** 9 + 7)))


t = int(input())
for i in range(0, t):
	n = int(input())
	print((4 * n * n * n + 3 * n * n - n) // 6 * 2022 % 1000000007)


for t in range(int(input())):
	n = int(input())
	a = n * (n + 1) * (4 * n + 5) // 6 - n * n - n
	print(a * 2022 % 1000000007)


for i in range(int(input())):
	a = int(input())
	p = a * (a + 1) * (4 * a - 1) * 2022 // 6
	print(p % 1000000007)