题目描述

给定一个数$n$,表示有一个 $n \times n$ 的方格。每个格子里都有一个数，第 $i$ 行第 $j$ 列的格子值为 $i⋅j$。现在Hawkins要从 $(1,1)$ 走到 $(n,n)$,每次只能从 $(i,j)$ 走到 $(i,j+1)$ 或 $(i+1,j)$, 每走到一个格子就能获得格子中的一个数，最大化数字之和。

输入格式

每个测试点包含多个测试样例。第一行包含测试样例的数量 $t$, 接下来 $t$ 行每行一个数 $n$。表示有 $n$ 行和 $n$ 列。

输出格式

共 $t$ 行，每行一个数，表所经过的格子乘 2022 后除以 $10^9 + 7$ 的余数。

样例

4
2
3
50
1000000000

14154
44484
171010650
999589541