// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } mod mint { use std::ops::{Add, AddAssign, Div, Mul, Rem, Sub}; #[derive(Copy, Clone)] pub struct Mint { x: T, mo: T, } impl Mint where T: Copy, T: Rem, T: Add, { pub fn new(x: T, mo: T) -> Mint { Mint { x: (x % mo + mo) % mo, mo: mo, } } } impl Mint where T: Copy, { pub fn val(&self) -> T { self.x } pub fn mo(&self) -> T { self.mo } } impl Add for Mint where T: Copy, T: Add, T: Rem, { type Output = Mint; fn add(self, rhs: T) -> Mint { Mint::new(self.val() + rhs % self.mo(), self.mo()) } } impl Add> for Mint where T: Copy, Mint: Add>, { type Output = Mint; fn add(self, rhs: Mint) -> Mint { self + rhs.val() } } impl Sub for Mint where T: Copy, T: Add, T: Sub, T: Rem, { type Output = Mint; fn sub(self, rhs: T) -> Mint { Mint::new(self.val() - rhs % self.mo(), self.mo()) } } impl Sub> for Mint where T: Copy, Mint: Sub>, { type Output = Mint; fn sub(self, rhs: Mint) -> Mint { self - rhs.val() } } impl Mul for Mint where T: Copy, T: Add, T: Mul, T: Rem, { type Output = Mint; fn mul(self, rhs: T) -> Mint { Mint::new(self.val() * rhs % self.mo(), self.mo()) } } impl Mul> for Mint where T: Copy, Mint: Mul>, { type Output = Mint; fn mul(self, rhs: Mint) -> Mint { self * rhs.val() } } impl std::fmt::Display for Mint where T: Copy + std::fmt::Display, { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.val()) } } } use mint::Mint; pub trait NextPermutation { fn next_permutation(&mut self) -> bool; } impl NextPermutation for [T] { fn next_permutation(&mut self) -> bool { if self.is_empty() { return false; } let mut i = self.len() - 1; while i > 0 && self[i - 1] >= self[i] { i -= 1; } if i == 0 { return false; } let mut j = self.len() - 1; while self[i - 1] >= self[j] { j -= 1; } self.swap(i - 1, j); self[i..].reverse(); return true; } } fn f(n: usize) -> i32 { let mut v = (0..n).collect::>(); let mut res = 0; loop { if v.iter().zip(0..n).all(|(&x, i)| x != i && x != n - i - 1) { res += 1; } if !v.next_permutation() { break; } } res } fn main() { input! { n: usize, } let mo = 998244353; let mut a = Mint::new(1, mo); for i in 1..=n { a = a * Mint::new(i, mo); } let mut b = vec![Mint::new(0, mo); n + 2]; b[2] = Mint::new(1, mo); for i in 3..=n { b[i] = Mint::new(i - 1, mo) * (b[i - 1] + b[i - 2]); } let b = b[n]; for i in 0..10 { // println!("{} {}", i, f(i)); // 0 1 // 1 0 // 2 0 // 3 0 // 4 4 // 5 16 // 6 80 // 7 672 // 8 4752 // 9 48768 // https://oeis.org/A003471 } let mut c = vec![Mint::new(0, mo); n + 2]; c[0] = Mint::new(1, mo); for i in 4..=n { if i % 2 == 0 { c[i] = Mint::new(i - 1, mo) * c[i - 1] + Mint::new(2 * (i - 2), mo) * c[i - 4]; } else { c[i] = Mint::new(i - 1, mo) * c[i - 1] + Mint::new(2 * (i - 1), mo) * c[i - 2]; } } let c = c[n]; println!("{}", a - b * 2 + c); }