题解见注释

/*    设至少有i行，j列是一种颜色的方案数为 f(i,j)	那么：	    1.i==0||j==0 时 , f(i,j) = C(n,i) * C(n,j) * 3^( (n-i)*(n-j) + i+j )		2.否则 , f(i,j) = C(n,i) * C(n,j) * 3^( (n-i)*(n-j) + 1 )		给上 f(i,j) 一个 (-1)^(i+j) 的容斥系数加起来 ((-1)^(i+j) = (-1)^(n-i+n-j))： 		3 * C(n,i)*(-1)^(n-i) * C(n,j)*(-1)^(n-j) * (3^(n-i))^(n-j)	3 * C(n,i)*(-1)^(n-i) * C(n,j) * (-3^(n-i))^(n-j)	3 * C(n,i)*(-1)^(n-i) *  ( (1-3^(n-i))^n - (-1)^n * 3^((n-i)*n))			考虑一种恰好有 I行,J列 是一种颜色的方案 , 	它会在 f(i,j) 中被算 C(I,i) * C(J,j) 次.		so 只要给 f(i,j) 一个 (-1)^(i+j) 的容斥系数 加起来得到 sum , 	那么 sum 就是 没有一行且没有一列同色 (I+J==0) 的方案数了. 	补集转化一下就是答案. */#include
     
      #define ll long longusing namespace std;const int ha=998244353,N=1e6+5,mod=ha-1;inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}inline int ksm(int x,int y){	int an=1;	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;	return an;}int n,jc[N],ni[N],f[N],ans;inline void init(){	jc[0]=1;	for(int i=1;i<=n;i++) jc[i]=jc[i-1]*(ll)i%ha;	ni[n]=ksm(jc[n],ha-2);	for(int i=n;i;i--) ni[i-1]=ni[i]*(ll)i%ha;}inline int C(int x,int y){ return jc[x]*(ll)ni[y]%ha*(ll)ni[x-y]%ha;}inline void solve(){	ans=ksm(3,n*(ll)n%mod);	for(int i=1,now;i<=n;i++){		now=C(n,i)*(ll)ksm(3,(i+n*(ll)(n-i))%mod)%ha;		if(i&1) ADD(ans,ha-add(now,now));		else ADD(ans,add(now,now));	}		int tot=0;		for(int i=1;i<=n;i++)	    if(n-i&1) ADD(tot,ha-C(n,i)*(ll)add(ksm(add(1,ha-ksm(3,n-i)),n),(n&1)?ksm(3,n*(ll)(n-i)%mod):ha-ksm(3,n*(ll)(n-i)%mod))%ha);	    else ADD(tot,C(n,i)*(ll)add(ksm(add(1,ha-ksm(3,n-i)),n),(n&1)?ksm(3,n*(ll)(n-i)%mod):ha-ksm(3,n*(ll)(n-i)%mod))%ha);    /*    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            if(i+j&1) ADD(tot,ha-C(n,i)*(ll)C(n,j)%ha*(ll)ksm(3,(n-i)*(ll)(n-j)%mod));            else ADD(tot,C(n,i)*(ll)C(n,j)%ha*(ll)ksm(3,(n-i)*(ll)(n-j)%mod));    */        ADD(ans,tot*3ll%ha);    ans=add(ha-ans,ksm(3,n*(ll)n%mod));}int main(){	scanf("%d",&n),init();	solve(),printf("%d\n",ans);	return 0;}