ll@t;
rep(t){
	Mint@n;ll@m;
	Mint x=n**m;
	Mint y=n**(m/2);
	wt(x*(x+1)/2-y*(y+1)*(2y+1)/6);
}