//---------- begin union_find ---------- pub struct DSU { p: Vec, } impl DSU { pub fn new(n: usize) -> DSU { assert!(n < std::i32::MAX as usize); DSU { p: vec![-1; n] } } pub fn root(&self, mut x: usize) -> usize { assert!(x < self.p.len()); while self.p[x] >= 0 { x = self.p[x] as usize; } x } pub fn same(&self, x: usize, y: usize) -> bool { assert!(x < self.p.len() && y < self.p.len()); self.root(x) == self.root(y) } pub fn unite(&mut self, x: usize, y: usize) { assert!(x < self.p.len() && y < self.p.len()); let mut x = self.root(x); let mut y = self.root(y); if x == y { return; } if self.p[x] > self.p[y] { std::mem::swap(&mut x, &mut y); } self.p[x] += self.p[y]; self.p[y] = x as i32; } } //---------- end union_find ---------- fn read() -> (usize, usize, usize) { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let a = s .trim() .split_whitespace() .flat_map(|s| s.parse::()) .collect::>(); (a[0], a[1], a[2]) } fn dfs(bit: usize, k: usize, id: usize, v: &mut Vec, state: &mut Vec>) { if k == v.len() { state.push(v.clone()); return; } if bit >> k & 1 == 0 { dfs(bit, k + 1, id, v, state); } else if k > 0 && bit >> (k - 1) & 1 == 1 { v[k] = v[k - 1]; dfs(bit, k + 1, id, v, state); } else { for i in 1..=(id + 1) { v[k] = i; dfs(bit, k + 1, id.max(i), v, state); } } } fn valid(a: &[usize], b: &[usize]) -> bool { if b.iter().all(|b| *b == 0) { return a.iter().all(|a| *a <= 1); } let mut ok = true; for (a, b) in a.windows(2).zip(b.windows(2)) { ok &= a[0] == a[1] || b[0] == b[1] || (a[0] == 0 && b[0] == 0) || (a[1] == 0 && b[1] == 0); } let c = a.len(); let mut dsu = DSU::new(2 * c); for l in 0..c { let mut zero = false; let mut hole = false; for r in (l + 1)..c { zero |= a[r] == 0; hole |= a[r] == 0 && b[r] == 0; if a[l] == a[r] && a[l] > 0 { dsu.unite(l, r); ok &= !zero || hole; } } if l > 0 && b[l] == b[l - 1] && b[l] > 0 { dsu.unite(l + c, l - 1 + c); } if a[l] > 0 && b[l] > 0 { dsu.unite(l, l + c); } } for i in 0..c { if a[i] > 0 { ok &= (0..c).any(|k| b[k] > 0 && dsu.same(i, k + c)); } } for i in 0..c { for j in 0..i { if b[i] > 0 && b[j] > 0 { ok &= dsu.same(i + c, j + c) ^ (b[i] != b[j]); } } } ok } fn main() { let (r, c, n) = read(); let mut state = vec![]; for i in 0..(1 << c) { dfs(i, 0, 0, &mut vec![0; c], &mut state); } let mut trans = vec![vec![]; state.len()]; for (trans, a) in trans.iter_mut().zip(state.iter()) { for (to, b) in state.iter().enumerate() { if valid(&a, &b) { let mut x = vec![0; c + 2]; x[1..=c].copy_from_slice(a); let mut y = vec![0; c + 2]; y[1..=c].copy_from_slice(b); let mut add = 0; for (a, b) in x.windows(2).zip(y.windows(2)) { if (a[0] > 0) ^ (a[1] > 0) ^ (b[0] > 0) ^ (b[1] > 0) { add += 1; } } trans.push((to, add)); } } } const MOD: u64 = 998_244_353; let mut dp = vec![vec![0u64; n + 1]; state.len()]; dp[0][0] = 1; let mut ans = 0; for _ in 0..=r { let mut next = vec![vec![0u64; n + 1]; state.len()]; for (trans, dp) in trans.iter().zip(dp.iter()) { for (i, dp) in dp.iter().enumerate().filter(|p| *p.1 > 0) { for &(u, x) in trans.iter() { if i + x <= n { next[u][i + x] += *dp; } } } } dp = next; dp.iter_mut().flatten().for_each(|dp| *dp %= MOD); ans += dp[0][n]; dp[0].iter_mut().for_each(|dp| *dp = 0); dp[0][0] = 1; } ans %= MOD; println!("{}", ans); }