#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; struct unionfind{ vector par, sz; unionfind() {} unionfind(int n):par(n), sz(n, 1){ for(int i=0; isz[y]) swap(x, y); par[x]=y; sz[y]+=sz[x]; } bool same(int x, int y){ return find(x)==find(y); } int size(int x){ return sz[find(x)]; } }; using mint=modint998244353; int main() { int r, c, n; cin>>r>>c>>n; map, mint> dp[51]; for(int i=1; i<(1< v(c+2); int t=0; for(int j=0; j v0(c+2); for(int z=0; z, mint> ndp[51]; for(int i=1; i<=n; i++){ for(auto p:dp[i]){ auto v=p.first; for(int j=0; j<(1<0) uf.unite(k+1, k+1+c+2); }else{ if(v[k+1]<=0) uf.unite(k+1, k+1+c+2); } } for(int k=0; k w(c+2); for(int k=0; k0) cnt1++; if(w[k-1]>0) cnt1++; if(v[k]>0) cnt1++; if(v[k-1]>0) cnt1++; if(cnt1&1) cnt++; } if(j==0){ if(cnt==n && *max_element(v.begin(), v.end())==1){ ans+=p.second*(r-z); } continue; } if(cnt<=n) ndp[cnt][w]+=p.second; } } } for(int i=1; i<=n; i++) swap(dp[i], ndp[i]); } cout<