#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define reps(x, s) for(llint (x) = 0; (x) < (llint)(s).size(); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(),(x).end() #define outl(x) cout << x << endl #define SP << " " << #define inf 1e18 #define mod 998244353 using namespace std; typedef long long llint; typedef long long ll; typedef pair P; ll h, w, n, S; ll dp[55][135][55]; ll ns[135][1<<7], add[135][1<<7]; vector vec; map mp; string adapt(string s) { map tmp; ll id = 1; for(auto c : s){ if(c == '0') continue; if(tmp.count(c)) continue; tmp[c] = id++; } for(auto &c : s) c = tmp[c]; return s; } string s; void dfs(int p){ if(p == w+1){ ll cnt[4] = {}; bool flag[4] = {}; string t = adapt(s); for(auto c : t)cnt[c-'0']++; rep(i, 1, 3) if(cnt[i] != 0 && cnt[i] != 2) return; stack stk; for(auto c : t){ if(c == '0') continue; if(stk.size() && stk.top() == c) stk.pop(); else stk.push(c); } if(stk.size()) return; mp[t]; return; } rep(i, 0, 3){ s += '0'+i; dfs(p+1); s.pop_back(); } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> h >> w >> n; dfs(0); ll id = 0; for(auto p : mp) p.second = id++, vec.push_back(p.first); //cout << vec.size() << endl; S = vec.size(); //for(auto p : mp) cout << p.first << endl; //cout << mp.size() << endl; ll W = 1<= 2) flag = false; } string t; rep(k, 0, w) t += '0'; ll id = 10; rep(k, 0, w){ ll deg = 0; if(s[k] > '0') deg++; if(k < w && (j&(1<= 0 && (j&(1<<(k-1)))) deg++; if(deg == 3) flag = false; if(deg == 2 && s[k] != '0') add[i][j]++; if(deg == 1){ if(s[k] == '0') t[k] = '0' + (id++)/2, add[i][j]++; else t[k] = s[k]; } } //cout << t << endl; if(flag) ns[i][j] = mp[adapt(t)]; //cout << s << " " << j << " " << ns[i][j] << " " << add[i][j] << endl; } } dp[0][0][0] = 1; rep(i, 0, h){ rep(j, 0, S-1){ if(i > 0 && j == 0) continue; rep(k, 0, n){ rep(l, 0, W-1){ if(ns[j][l] == -1) continue; if(k+add[j][k] <= n) (dp[i+1][ns[j][l]][k+add[j][l]] += dp[i][j][k]) %= mod; } } } } cout << dp[h+1][0][n] << endl; return 0; }