来自颠倒的恶魔再次攻击了霍金斯。艾尔想要联系迈克,并以尽可能多的方式杀死恶魔狗。
霍金斯可以表示为 $$$n \times n$$$ 网格。第 $$$i$$$ 行、第 $$$j$$$ 列的单元格中的 Demodog 数量为 $$$i \cdot j$$$。 El 位于网格的位置 $$$(1, 1)$$$,她必须到达 $$$(n, n)$$$ 才能找到 Mike。
她唯一可以移动的方向是向右(从 $$$(i, j)$$$ 到 $$$(i, j + 1)$$$)和向下(从 $$$(i, j)$$$ 到 $$$(i + 1, j)$$$)。她无法走出网格,因为边界处有通往颠倒的门。
考虑到她杀死了她所访问的单元格(包括开始单元格和结束单元格)中的所有演示狗,计算她在途中可以杀死的演示狗 $$$\mathrm{ans}$$$ 的最大可能数量。
打印 $$$2022 \cdot \mathrm{ans}$$$ 模 $$$10^9 + 7$$$。对 $$$10^9 + 7$$$ 取模,因为结果可能太大并乘以 $$$2022$$$ 因为我们再也不会看到它了!
(注意,您首先乘以 $$$2022$$$,然后才取余数。)
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — 网格的大小。
输出
对于每个测试用例,打印一个整数 - 可杀死的 Demodog 的最大数量乘以 $$$2022$$$,模 $$$10^9 + 7$$$。
示例
输入 #1
4 2 3 50 1000000000
输出 #1
14154 44484 171010650 999589541
注意
在第一个测试用例中,对于她选择的任何路径,要杀死的 Demodog 数量将为 $$$7$$$,因此答案将为 $$$2022 \cdot 7 = 14154$$$。