//---------- 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 init(&mut self) { self.p.iter_mut().for_each(|p| *p = -1); } 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) -> Option<(usize, 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 None; } 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; Some((x, y)) } pub fn parent(&self, x: usize) -> Option { assert!(x < self.p.len()); let p = self.p[x]; if p >= 0 { Some(p as usize) } else { None } } pub fn sum(&self, mut x: usize, mut f: F) -> usize where F: FnMut(usize), { while let Some(p) = self.parent(x) { f(x); x = p; } x } pub fn size(&self, x: usize) -> usize { assert!(x < self.p.len()); let r = self.root(x); (-self.p[r]) as usize } } //---------- end union_find ---------- // ---------- begin max flow (Dinic) ---------- mod maxflow { pub trait MaxFlowCapacity: Copy + Ord + std::ops::Add + std::ops::Sub { fn zero() -> Self; fn inf() -> Self; } macro_rules! impl_primitive_integer_capacity { ($x:ty, $y:expr) => { impl MaxFlowCapacity for $x { fn zero() -> Self { 0 } fn inf() -> Self { $y } } }; } impl_primitive_integer_capacity!(u32, std::u32::MAX); impl_primitive_integer_capacity!(u64, std::u64::MAX); impl_primitive_integer_capacity!(i32, std::i32::MAX); impl_primitive_integer_capacity!(i64, std::i64::MAX); #[derive(Clone)] struct Edge { to_: u32, inv_: u32, cap_: Cap, } impl Edge { fn new(to: usize, inv: usize, cap: Cap) -> Self { Edge { to_: to as u32, inv_: inv as u32, cap_: cap, } } fn to(&self) -> usize { self.to_ as usize } fn inv(&self) -> usize { self.inv_ as usize } } impl Edge { fn add(&mut self, cap: Cap) { self.cap_ = self.cap_ + cap; } fn sub(&mut self, cap: Cap) { self.cap_ = self.cap_ - cap; } fn cap(&self) -> Cap { self.cap_ } } pub struct Graph { graph: Vec>>, } #[allow(dead_code)] pub struct EdgeIndex { src: usize, dst: usize, x: usize, y: usize, } impl Graph { pub fn new(size: usize) -> Self { Self { graph: vec![vec![]; size], } } pub fn add_edge(&mut self, src: usize, dst: usize, cap: Cap) -> EdgeIndex { assert!(src.max(dst) < self.graph.len()); assert!(cap >= Cap::zero()); assert!(src != dst); let x = self.graph[src].len(); let y = self.graph[dst].len(); self.graph[src].push(Edge::new(dst, y, cap)); self.graph[dst].push(Edge::new(src, x, Cap::zero())); EdgeIndex { src, dst, x, y } } // src, dst, used, intial_capacity #[allow(dead_code)] pub fn get_edge(&self, e: &EdgeIndex) -> (usize, usize, Cap, Cap) { let max = self.graph[e.src][e.x].cap() + self.graph[e.dst][e.y].cap(); let used = self.graph[e.dst][e.y].cap(); (e.src, e.dst, used, max) } pub fn flow(&mut self, src: usize, dst: usize) -> Cap { let size = self.graph.len(); assert!(src.max(dst) < size); assert!(src != dst); let mut queue = std::collections::VecDeque::new(); let mut level = vec![0; size]; let mut it = vec![0; size]; let mut ans = Cap::zero(); loop { (|| { level.clear(); level.resize(size, 0); level[src] = 1; queue.clear(); queue.push_back(src); while let Some(v) = queue.pop_front() { let d = level[v] + 1; for e in self.graph[v].iter() { let u = e.to(); if e.cap() > Cap::zero() && level[u] == 0 { level[u] = d; if u == dst { return; } queue.push_back(u); } } } })(); if level[dst] == 0 { break; } it.clear(); it.resize(size, 0); loop { let f = self.dfs(dst, src, Cap::inf(), &mut it, &level); if f == Cap::zero() { break; } ans = ans + f; } } ans } fn dfs(&mut self, v: usize, src: usize, cap: Cap, it: &mut [usize], level: &[u32]) -> Cap { if v == src { return cap; } while let Some((u, inv)) = self.graph[v].get(it[v]).map(|p| (p.to(), p.inv())) { if level[u] + 1 == level[v] && self.graph[u][inv].cap() > Cap::zero() { let cap = cap.min(self.graph[u][inv].cap()); let c = self.dfs(u, src, cap, it, level); if c > Cap::zero() { self.graph[v][it[v]].add(c); self.graph[u][inv].sub(c); return c; } } it[v] += 1; } Cap::zero() } } } // ---------- end max flow (Dinic) ---------- // ---------- begin ModInt ---------- mod modint { #[allow(dead_code)] pub struct Mod; impl ConstantModulo for Mod { const MOD: u32 = 998_244_353; } use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; } pub trait ConstantModulo { const MOD: u32; } impl Modulo for T where T: ConstantModulo, { fn modulo() -> u32 { T::MOD } } pub struct ModInt(pub u32, PhantomData); impl Clone for ModInt { fn clone(&self) -> Self { ModInt::new_unchecked(self.0) } } impl Copy for ModInt {} impl Add for ModInt { type Output = ModInt; fn add(self, rhs: Self) -> Self::Output { let mut d = self.0 + rhs.0; if d >= T::modulo() { d -= T::modulo(); } ModInt::new_unchecked(d) } } impl AddAssign for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt { type Output = ModInt; fn sub(self, rhs: Self) -> Self::Output { let mut d = self.0 - rhs.0; if d >= T::modulo() { d += T::modulo(); } ModInt::new_unchecked(d) } } impl SubAssign for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt { type Output = ModInt; fn mul(self, rhs: Self) -> Self::Output { let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64; ModInt::new_unchecked(v as u32) } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { if self.0 == 0 { Self::zero() } else { Self::new_unchecked(T::modulo() - self.0) } } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::fmt::Debug for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt { fn from(val: usize) -> ModInt { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl From for ModInt { fn from(val: u64) -> ModInt { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl From for ModInt { fn from(val: i64) -> ModInt { let m = T::modulo() as i64; ModInt::new((val % m + m) as u32) } } #[allow(dead_code)] impl ModInt { pub fn new_unchecked(d: u32) -> Self { ModInt(d, PhantomData) } pub fn zero() -> Self { ModInt::new_unchecked(0) } pub fn one() -> Self { ModInt::new_unchecked(1) } pub fn is_zero(&self) -> bool { self.0 == 0 } } #[allow(dead_code)] impl ModInt { pub fn new(d: u32) -> Self { ModInt::new_unchecked(d % T::modulo()) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(&self) -> Self { assert!(self.0 != 0); self.pow(T::modulo() as u64 - 2) } } } // ---------- end ModInt ---------- // ---------- begin Precalc ---------- mod precalc { use super::modint::*; #[allow(dead_code)] pub struct Precalc { inv: Vec>, fact: Vec>, ifact: Vec>, } #[allow(dead_code)] impl Precalc { pub fn new(n: usize) -> Precalc { let mut inv = vec![ModInt::one(); n + 1]; let mut fact = vec![ModInt::one(); n + 1]; let mut ifact = vec![ModInt::one(); n + 1]; for i in 2..(n + 1) { fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32); } ifact[n] = fact[n].inv(); if n > 0 { inv[n] = ifact[n] * fact[n - 1]; } for i in (1..n).rev() { ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32); inv[i] = ifact[i] * fact[i - 1]; } Precalc { inv: inv, fact: fact, ifact: ifact, } } pub fn inv(&self, n: usize) -> ModInt { assert!(n > 0); self.inv[n] } pub fn fact(&self, n: usize) -> ModInt { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt { self.ifact[n] } pub fn perm(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[n - k] } pub fn comb(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[k] * self.ifact[n - k] } } } // ---------- end Precalc ---------- use modint::*; type M = ModInt; // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- use std::cmp::*; use std::collections::*; type Map = BTreeMap; fn run() { let free = 2; let mut trans = Map::new(); for l in 1..=(free + 1) { for r in 1..=(free + 1) { if (l, r) == (1, 1) { continue; } for bit in 0usize..(1 << (l * r)) { let mut dsu = DSU::new(l + r); let mut g = maxflow::Graph::new(l + r + 2); let src = l + r; let dst = src + 1; for i in 0..l { for j in 0..r { let x = i * r + j; if bit >> x & 1 == 1 { dsu.unite(i, l + j); g.add_edge(i, l + j, 1u32); } } } for i in 0..l { g.add_edge(src, i, 1); } for i in 0..r { g.add_edge(l + i, dst, 1); } if dsu.size(0) == l + r { let cnt = bit.count_ones() as usize; let f = g.flow(src, dst) as usize; if cnt <= f + free { *trans.entry((l, r, cnt, f)).or_insert(M::zero()) += M::one(); } } } } } input!(n: usize, m: usize, k: usize); let pc = precalc::Precalc::new(n + m + k); let mut dp = Map::new(); dp.insert((0, 0, 0, 0), M::one()); let mut ans = M::zero(); while let Some((&key, &value)) = dp.iter().next() { dp.remove(&key); let (x, y, e, f) = key; let mut cond = true; cond &= x <= n; cond &= y <= m; cond &= e <= k; cond &= f + free >= e; if !cond { continue; } if e - f == free { let req = k - free - f; if req + x <= n && req + y <= m { let mut way = value; way *= pc.comb(n, req + x); way *= pc.comb(m, req + y); way *= pc.comb(req + x, x); way *= pc.comb(req + y, y); way *= pc.fact(req); ans += way; } continue; } for (&(a, b, c, d), &w) in trans.iter() { let mut w = w * value; w *= pc.comb(x + a - 1, a - 1); w *= pc.comb(y + b, b); *dp.entry((x + a, y + b, e + c, f + d)).or_insert(M::zero()) += w; } } println!("{}", ans); } fn main() { run(); }