40分钟一波乱搞居然自己做出来了，开心！
答案是显然可以转化成：( m{总方案数-没有任何一行或一列同色的方案数})
为啥这么化呢。。。显然后面那个东西比直接算答案简洁吧。
没有任何一行一列，就是恰好 (0) 行 (0) 列同色，强行把 恰好 拉出来反演掉。
令 (g(x,y)) 表示钦定 (x) 行 (y) 列同色得到的方案数，(f(x,y)) 表示至少 (x) 行 (y) 列同色的方案数
高维二项式反演的公式就是上面那玩意，瞎猜都能猜出来，事实上就是对的/cy。
但是不知道也没关系，因为这题只要求 (g(0,0)) ，所以可以直接容斥而不用管扩展性这么强的结论，我就是容斥想的，做完之后看题解看到了上面那个结论。
首先得想个办法把 (f(x,y)) 表示出来。
分成两部分考虑，一部分是任选同色的 (x) 行 (y) 列，一部分是在这 (x) 行 (y) 列之外的格子。
-
第一部分
- 如果 (x>0,y>0) ，那么这 (x) 行 (y) 列必然同色，方案数乘 (3)。
- 如果 (x=0 or y=0) ，那么要么全是行，要么全是列，颜色随便取，所以方案数乘 (3^{x+y})
-
第二部分
剩余格子个数应该是 ((n-x)(n-y)) ，因为有 (x) 行 (y) 列被占用了。所以方案数乘上 (3^{(n-x)(n-y)})
整合一下：
然而到此为止还是 (O(n^2)) 级别的复杂度。（有可能带单只快速幂 (log) ，但是无关紧要，下同）
把 (f(x,y)) 往 (g(x,y)) 的式子里大力带入然后整理。由于 (x=0 or y=0) 的情况数很少，暴力 (O(n)) 算都可以，所以直接算 (x>0,y>0) 的情况了。
我是特判了 (i=0) 的情况，(O(n)) 计算，然后枚举 (i) 的过程中再特判 (j=0) 的情况的。
不知道你看出来了啥没有，反正我看了大概1分钟就会做了（
现在瓶颈就是下面这玩意对吧，把这个算出来就可以 (O(n)) 了。
或许式子应该写的更好看一点？令 (t=3^{n-i})
直接二项式定理就好了，不要忘记 (j=0) 的情况要减掉。
#define mod 998244353
const int N=1000005;
namespace math{
int fac[N],ifc[N];
inline int qpow(int n,int k){int res=1;for(;k;k>>=1,n=1ll*n*n%mod)if(k&1)res=1ll*n*res%mod;return res;}
void fmod(int&x){x-=mod,x+=x>>31&mod;}
int comb(int n,int m){return n<m?0:1ll*fac[n]*ifc[m]%mod*ifc[n-m]%mod;}
void initmath(const int&n=N-1){
fac[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*i*fac[i-1]%mod;
ifc[n]=qpow(fac[n],mod-2);for(int i=n-1;i>=0;--i)ifc[i]=1ll*(i+1)*ifc[i+1]%mod;
}
}
using math::qpow;
using math::fmod;
int n,ans;
int f(int x,int y){
return 1ll*qpow(3,1ll*(n-x)*(n-y)%(mod-1))*((!x||!y)?qpow(3,x+y):3)%mod;
}
signed main(){
math::initmath();
n=read();
for(int i=1;i<=n;++i){
const int t=qpow(3,n-i);
int res=3ll*(qpow(t-1,n)-qpow(t,n)+mod)%mod;
fmod(res+=1ll*qpow(t,n)*qpow(3,i)%mod);
fmod(ans+=1ll*math::comb(n,i)*(i&1?mod-res:res)%mod);
}
for(int i=0;i<=n;++i)fmod(ans+=1ll*math::comb(n,i)*(i&1?mod-f(0,i):f(0,i))%mod);
fmod(ans=qpow(3,1ll*n*n%(mod-1))-ans+mod);
cout<<ans<<'
';
}