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 nn×n grid. The number of Demodogs in a cell at the ii -th row and the jj -th column is i \cdot ji⋅j . El is at position (1, 1)(1,1) of the grid, and she has to reach (n, n)(n,n) where she can find Mike.
The only directions she can move are the right (from (i, j)(i,j) to (i, j + 1)(i,j+1) ) and the down (from (i, j)(i,j) to (i + 1, j)(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}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}2022⋅ans modulo 10^9 + 7109+7 . Modulo 10^9 + 7109+7 because the result can be too large and multiplied by 20222022 because we are never gonna see it again!
(Note, you firstly multiply by 20222022 and only after that take the remainder.)
输入格式Each test contains multiple test cases. The first line contains the number of test cases tt ( 1 \leq t \leq 10^41≤t≤104 ). Description of the test cases follows.
The first line of each test case contains one integer nn ( 2 \leq n \leq 10^92≤n≤109 ) — the size of the grid.
输出格式For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by 20222022 , modulo 10^9 + 7109+7 .
题意翻译给定一个数nn,表示有一个 n \times nn×n 的方格。每个格子里都有一个数，第 ii 行第 jj 列的格子值为 i⋅ji⋅j。现在Hawkins要从 (1,1)(1,1) 走到 (n,n)(n,n),每次只能从 (i,j)(i,j) 走到 (i,j+1)(i,j+1) 或 (i+1,j)(i+1,j), 每走到一个格子就能获得格子中的一个数，大化数字之和。
输入格式每个测试点包含多个测试样例。第一行包含测试样例的数量 tt, 接下来 tt 行每行一个数 nn。表示有 nn 行和 nn 列。
输出格式共 tt 行，每行一个数，表所经过的格子乘 2022 后除以 10^9 + 7109+7 的余数。
输入输出样例输入 #1复制
4 2 3 50 1000000000
输出 #1复制
14154 44484 171010650 999589541说明/提示
In the first test case, for any path chosen by her the number of Demodogs to be killed would be 77 , so the answer would be 2022 \cdot 7 = 141542022⋅7=14154 .
题解
#importusing namespace std;
#define int long long
int p[4000040];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int ksm(int a,int b,int mod)
{
int res=1;
while(b)
{
if(b&1)
res=res*a,res%=mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int sum[20000020];
const int mod=1e9+7;
signed main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int ans=n*(n + 1)%mod*(4*n - 1)%mod*ksm(6,mod-2,mod)%mod;
cout< 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
