#![allow(dead_code, unused_imports, unused_macros, non_snake_case)] use proconio::{ input, input_interactive, marker::{Bytes, Chars, Usize1}, }; fn main() { input! { n: usize } const MOD: i64 = 998244353; // dp[i][j] = i 文字使って深さが j である (個数, 総和) let mut prv = vec![(0, 0); n]; let mut nxt = vec![(0, 0); n]; prv[0] = (1, 0); for _ in 0..n { for j in 0..n { // ( if j > 0 { nxt[j].0 += prv[j - 1].0; nxt[j].1 += prv[j - 1].1; } // ) if j < n - 1 { nxt[j].0 += prv[j + 1].0; nxt[j].1 += prv[j + 1].1 + prv[j + 1].0 * j as i64 % MOD; } nxt[j].0 %= MOD; nxt[j].1 %= MOD; } std::mem::swap(&mut prv, &mut nxt); nxt.fill((0, 0)); } println!("{}", prv[0].1); }