997C - Sky Full of Stars - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int mod=998244353,n;

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
long long fact[maxn],revfact[maxn];

void aval(){
	fact[0]=1;
	for(int i=1;i<maxn;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	//cout<<fact[maxn-1]<<"\n";
	revfact[maxn-1]=mypow(fact[maxn-1],mod-2);
	for(int i=maxn-2;i>=0;i--){
		revfact[i]=revfact[i+1]*(i+1)%mod;
	}
}

int c(int i,int j){
	if(i<0||j<0||i<j){
		return 0;
	}
	int ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n;
	long long res=0;
	long long cnt=1ll*n*n;
	for(int i=1;i<=n;i++){
		cnt-=n;
		long long fake=1ll*c(n,i)*mypow(3,cnt)%mod*mypow(3,i)%mod;
		//cout<<c(n,i)<<" "<<n<<" "<<i<<" "<<fact[1]<<" "<<revfact[1]<<" "<<revfact[0]<<"\n";
		if((i&1)==0){
			res+=mod+mod-fake;
		}
		else{
			res+=fake;
		}
		res%=mod;
	}
	//cout<<res<<"\n";
	cnt=1ll*n*n;
	for(int i=1;i<=n;i++){
		cnt-=n;
		long long fake=1ll*c(n,i)*mypow(3,cnt)%mod*((mypow(3,i)+mod-3)%mod)%mod;
		fake+=1ll*c(n,i)*3*mypow(mypow(3,n-i)-1,n)%mod;
		fake%=mod;
		//cout<<i<<" "<<fake<<"\n";
		if((i&1)==0){
			res+=mod+mod-fake;
		}
		else{
			res+=fake;
		}
		res%=mod;
	}
	cout<<res<<"\n";
}