pub trait Zero: PartialEq + Sized {
    fn zero() -> Self;
    #[inline]
    fn is_zero(&self) -> bool {
        self == &Self::zero()
    }
}
pub trait One: PartialEq + Sized {
    fn one() -> Self;
    #[inline]
    fn is_one(&self) -> bool {
        self == &Self::one()
    }
}
macro_rules ! zero_one_impls {($ ({$ Trait : ident $ method : ident $ ($ t : ty ) *, $ e : expr } ) * ) => {$ ($ (impl $ Trait for $ t {# [inline ] fn $ method () -> Self {$ e } } ) * ) * } ; }
zero_one_impls ! ({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128 , 0 } {Zero zero f32 f64 , 0. } {One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128 , 1 } {One one f32 f64 , 1. } );
pub trait IterScan: Sized {
    type Output;
    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>;
}
pub trait MarkedIterScan: Sized {
    type Output;
    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output>;
}
#[derive(Clone, Debug)]
pub struct Scanner<'a> {
    iter: std::str::SplitAsciiWhitespace<'a>,
}
mod scanner_impls {
    use super::*;
    impl<'a> Scanner<'a> {
        #[inline]
        pub fn new(s: &'a str) -> Self {
            let iter = s.split_ascii_whitespace();
            Self { iter }
        }
        #[inline]
        pub fn scan<T: IterScan>(&mut self) -> <T as IterScan>::Output {
            <T as IterScan>::scan(&mut self.iter).expect("scan error")
        }
        #[inline]
        pub fn mscan<T: MarkedIterScan>(&mut self, marker: T) -> <T as MarkedIterScan>::Output {
            marker.mscan(&mut self.iter).expect("scan error")
        }
        #[inline]
        pub fn scan_vec<T: IterScan>(&mut self, size: usize) -> Vec<<T as IterScan>::Output> {
            (0..size)
                .map(|_| <T as IterScan>::scan(&mut self.iter).expect("scan error"))
                .collect()
        }
        #[inline]
        pub fn iter<'b, T: IterScan>(&'b mut self) -> ScannerIter<'a, 'b, T> {
            ScannerIter {
                inner: self,
                _marker: std::marker::PhantomData,
            }
        }
    }
    macro_rules ! iter_scan_impls {($ ($ t : ty ) * ) => {$ (impl IterScan for $ t {type Output = Self ; # [inline ] fn scan <'a , I : Iterator < Item = &'a str >> (iter : & mut I ) -> Option < Self > {iter . next () ?. parse ::<$ t > () . ok () } } ) * } ; }
    iter_scan_impls ! (char u8 u16 u32 u64 usize i8 i16 i32 i64 isize f32 f64 u128 i128 String );
    macro_rules ! iter_scan_tuple_impl {($ ($ T : ident ) * ) => {impl <$ ($ T : IterScan ) ,*> IterScan for ($ ($ T , ) * ) {type Output = ($ (<$ T as IterScan >:: Output , ) * ) ; # [inline ] fn scan <'a , It : Iterator < Item = &'a str >> (_iter : & mut It ) -> Option < Self :: Output > {Some (($ (<$ T as IterScan >:: scan (_iter ) ?, ) * ) ) } } } ; }
    iter_scan_tuple_impl!();
    iter_scan_tuple_impl!(A);
    iter_scan_tuple_impl ! (A B );
    iter_scan_tuple_impl ! (A B C );
    iter_scan_tuple_impl ! (A B C D );
    iter_scan_tuple_impl ! (A B C D E );
    iter_scan_tuple_impl ! (A B C D E F );
    iter_scan_tuple_impl ! (A B C D E F G );
    iter_scan_tuple_impl ! (A B C D E F G H );
    iter_scan_tuple_impl ! (A B C D E F G H I );
    iter_scan_tuple_impl ! (A B C D E F G H I J );
    iter_scan_tuple_impl ! (A B C D E F G H I J K );
    pub struct ScannerIter<'a, 'b, T> {
        inner: &'b mut Scanner<'a>,
        _marker: std::marker::PhantomData<fn() -> T>,
    }
    impl<'a, 'b, T: IterScan> Iterator for ScannerIter<'a, 'b, T> {
        type Item = <T as IterScan>::Output;
        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            <T as IterScan>::scan(&mut self.inner.iter)
        }
    }
}
pub mod marker {
    use super::*;
    use std::{iter::FromIterator, marker::PhantomData};
    #[derive(Debug, Copy, Clone)]
    pub struct Usize1;
    impl IterScan for Usize1 {
        type Output = usize;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            Some(<usize as IterScan>::scan(iter)?.checked_sub(1)?)
        }
    }
    #[derive(Debug, Copy, Clone)]
    pub struct Chars;
    impl IterScan for Chars {
        type Output = Vec<char>;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            Some(iter.next()?.chars().collect())
        }
    }
    #[derive(Debug, Copy, Clone)]
    pub struct CharsWithBase(pub char);
    impl MarkedIterScan for CharsWithBase {
        type Output = Vec<usize>;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            Some(
                iter.next()?
                    .chars()
                    .map(|c| (c as u8 - self.0 as u8) as usize)
                    .collect(),
            )
        }
    }
    #[derive(Debug, Copy, Clone)]
    pub struct Collect<T: IterScan, B: FromIterator<<T as IterScan>::Output>> {
        size: usize,
        _marker: PhantomData<fn() -> (T, B)>,
    }
    impl<T: IterScan, B: FromIterator<<T as IterScan>::Output>> Collect<T, B> {
        pub fn new(size: usize) -> Self {
            Self {
                size,
                _marker: PhantomData,
            }
        }
    }
    impl<T: IterScan, B: FromIterator<<T as IterScan>::Output>> MarkedIterScan for Collect<T, B> {
        type Output = B;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            Some(
                (0..self.size)
                    .map(|_| <T as IterScan>::scan(iter).expect("scan error"))
                    .collect::<B>(),
            )
        }
    }
}
#[macro_export]
macro_rules ! min {($ e : expr ) => {$ e } ; ($ e : expr , $ ($ es : expr ) ,+ ) => {std :: cmp :: min ($ e , min ! ($ ($ es ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! chmin {($ dst : expr , $ ($ src : expr ) ,+ ) => {{let x = std :: cmp :: min ($ dst , min ! ($ ($ src ) ,+ ) ) ; $ dst = x ; } } ; }
#[macro_export]
macro_rules ! max {($ e : expr ) => {$ e } ; ($ e : expr , $ ($ es : expr ) ,+ ) => {std :: cmp :: max ($ e , max ! ($ ($ es ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! chmax {($ dst : expr , $ ($ src : expr ) ,+ ) => {{let x = std :: cmp :: max ($ dst , max ! ($ ($ src ) ,+ ) ) ; $ dst = x ; } } ; }
pub trait Modulus {
    fn get_modulus() -> u32;
    #[inline]
    fn modulo(x: u32) -> u32 {
        x % Self::get_modulus()
    }
}
#[allow(unused_macros)]
macro_rules! make_modulus {
    ($ t : ident , $ e : expr ) => {
        pub struct $t {}
        impl Modulus for $t {
            #[inline]
            fn get_modulus() -> u32 {
                const MODULUS: u32 = $e;
                MODULUS
            }
        }
    };
}
#[allow(unused_macros)]
macro_rules! make_dynamic_modulus {
    ($ t : ident , $ m : ident , $ e : expr ) => {
        pub struct $t {}
        static mut $m: u32 = $e;
        impl Modulus for $t {
            #[inline]
            fn get_modulus() -> u32 {
                unsafe { $m }
            }
        }
    };
}
pub mod modulus {
    use super::*;
    pub struct Modulo1000000007 {}
    impl Modulus for Modulo1000000007 {
        #[inline]
        fn get_modulus() -> u32 {
            const MODULUS: u32 = 1_000_000_007;
            MODULUS
        }
    }
    pub type MInt1000000007 = MInt<Modulo1000000007>;
    pub struct Modulo1000000009 {}
    impl Modulus for Modulo1000000009 {
        #[inline]
        fn get_modulus() -> u32 {
            const MODULUS: u32 = 1_000_000_009;
            MODULUS
        }
    }
    pub type MInt1000000009 = MInt<Modulo1000000009>;
    pub struct Modulo998244353 {}
    impl Modulus for Modulo998244353 {
        #[inline]
        fn get_modulus() -> u32 {
            const MODULUS: u32 = 998_244_353;
            MODULUS
        }
    }
    pub type MInt998244353 = MInt<Modulo998244353>;
    pub struct DynModulo {}
    static mut DYN_MODULUS: u32 = 1_000_000_007;
    impl Modulus for DynModulo {
        #[inline]
        fn get_modulus() -> u32 {
            unsafe { DYN_MODULUS }
        }
    }
    pub fn set_dyn_modulus(m: u32) {
        unsafe {
            DYN_MODULUS = m;
        }
    }
    pub type DynMInt = MInt<DynModulo>;
}
#[repr(transparent)]
pub struct MInt<M>
where
    M: Modulus,
{
    x: u32,
    _marker: std::marker::PhantomData<fn() -> M>,
}
mod mint_impls {
    use super::*;
    use std::{
        cmp::Ordering,
        fmt::{self, Debug},
        hash::{Hash, Hasher},
        iter::{Product, Sum},
        marker::PhantomData,
        mem::swap,
        num::ParseIntError,
        ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
        str::FromStr,
    };
    impl<M: Modulus> MInt<M> {
        #[inline]
        pub fn new(x: u32) -> Self {
            Self {
                x: M::modulo(x),
                _marker: PhantomData,
            }
        }
        #[inline]
        pub fn new_unchecked(x: u32) -> Self {
            Self {
                x,
                _marker: PhantomData,
            }
        }
        #[inline]
        pub fn inner(self) -> u32 {
            self.x
        }
        #[inline]
        pub fn get_mod() -> u32 {
            M::get_modulus()
        }
        #[inline]
        pub fn pow(mut self, mut y: usize) -> Self {
            let mut x = Self::one();
            while y > 0 {
                if y & 1 == 1 {
                    x *= self;
                }
                self *= self;
                y >>= 1;
            }
            x
        }
        #[inline]
        /// only prime modulus
        pub fn inv(self) -> Self {
            let mut a = self.x;
            let (mut b, mut u, mut s) = (M::get_modulus(), 1, 0);
            let k = a.trailing_zeros();
            a >>= k;
            for _ in 0..k {
                if u & 1 == 1 {
                    u += M::get_modulus();
                }
                u /= 2;
            }
            while a != b {
                if b < a {
                    swap(&mut a, &mut b);
                    swap(&mut u, &mut s);
                }
                b -= a;
                if s < u {
                    s += M::get_modulus();
                }
                s -= u;
                let k = b.trailing_zeros();
                b >>= k;
                for _ in 0..k {
                    if s & 1 == 1 {
                        s += M::get_modulus();
                    }
                    s /= 2;
                }
            }
            Self::new_unchecked(s)
        }
    }
    impl<M: Modulus> Clone for MInt<M> {
        #[inline]
        fn clone(&self) -> Self {
            Self {
                x: Clone::clone(&self.x),
                _marker: PhantomData,
            }
        }
    }
    impl<M: Modulus> Copy for MInt<M> {}
    impl<M: Modulus> Debug for MInt<M> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            Debug::fmt(&self.x, f)
        }
    }
    impl<M: Modulus> Default for MInt<M> {
        #[inline]
        fn default() -> Self {
            Self::zero()
        }
    }
    impl<M: Modulus> PartialEq for MInt<M> {
        #[inline]
        fn eq(&self, other: &Self) -> bool {
            PartialEq::eq(&self.x, &other.x)
        }
    }
    impl<M: Modulus> PartialOrd for MInt<M> {
        #[inline]
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            PartialOrd::partial_cmp(&self.x, &other.x)
        }
    }
    impl<M: Modulus> Eq for MInt<M> {}
    impl<M: Modulus> Ord for MInt<M> {
        #[inline]
        fn cmp(&self, other: &Self) -> Ordering {
            Ord::cmp(&self.x, &other.x)
        }
    }
    impl<M: Modulus> Hash for MInt<M> {
        #[inline]
        fn hash<H: Hasher>(&self, state: &mut H) {
            Hash::hash(&self.x, state)
        }
    }
    impl<M: Modulus> From<u32> for MInt<M> {
        #[inline]
        fn from(x: u32) -> Self {
            Self::new(x)
        }
    }
    impl<M: Modulus> From<u64> for MInt<M> {
        #[inline]
        fn from(x: u64) -> Self {
            Self::new_unchecked((x % M::get_modulus() as u64) as u32)
        }
    }
    impl<M: Modulus> From<usize> for MInt<M> {
        #[inline]
        fn from(x: usize) -> Self {
            Self::new_unchecked((x % M::get_modulus() as usize) as u32)
        }
    }
    impl<M: Modulus> From<i32> for MInt<M> {
        #[inline]
        fn from(x: i32) -> Self {
            let x = x % M::get_modulus() as i32;
            if x < 0 {
                Self::new_unchecked((x + M::get_modulus() as i32) as u32)
            } else {
                Self::new_unchecked(x as u32)
            }
        }
    }
    impl<M: Modulus> From<i64> for MInt<M> {
        #[inline]
        fn from(x: i64) -> Self {
            let x = x % M::get_modulus() as i64;
            if x < 0 {
                Self::new_unchecked((x + M::get_modulus() as i64) as u32)
            } else {
                Self::new_unchecked(x as u32)
            }
        }
    }
    impl<M: Modulus> From<isize> for MInt<M> {
        #[inline]
        fn from(x: isize) -> Self {
            let x = x % M::get_modulus() as isize;
            if x < 0 {
                Self::new_unchecked((x + M::get_modulus() as isize) as u32)
            } else {
                Self::new_unchecked(x as u32)
            }
        }
    }
    impl<M: Modulus> Add for MInt<M> {
        type Output = Self;
        #[inline]
        fn add(self, rhs: Self) -> Self::Output {
            let mut x = self.x + rhs.x;
            if x >= M::get_modulus() {
                x -= M::get_modulus();
            }
            Self::new_unchecked(x)
        }
    }
    impl<M: Modulus> Sub for MInt<M> {
        type Output = Self;
        #[inline]
        fn sub(self, rhs: Self) -> Self::Output {
            if self.x < rhs.x {
                Self::new_unchecked(self.x + M::get_modulus() - rhs.x)
            } else {
                Self::new_unchecked(self.x - rhs.x)
            }
        }
    }
    impl<M: Modulus> Mul for MInt<M> {
        type Output = Self;
        #[inline]
        fn mul(self, rhs: Self) -> Self::Output {
            Self::new_unchecked((self.x as u64 * rhs.x as u64 % M::get_modulus() as u64) as u32)
        }
    }
    impl<M: Modulus> Div for MInt<M> {
        type Output = Self;
        #[inline]
        fn div(self, rhs: Self) -> Self::Output {
            self.mul(rhs.inv())
        }
    }
    impl<M: Modulus> Neg for MInt<M> {
        type Output = Self;
        #[inline]
        fn neg(self) -> Self::Output {
            if self.x == 0 {
                Self::zero()
            } else {
                Self::new_unchecked(M::get_modulus() - self.x)
            }
        }
    }
    impl<M: Modulus> Sum for MInt<M> {
        #[inline]
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::zero(), Add::add)
        }
    }
    impl<M: Modulus> Product for MInt<M> {
        #[inline]
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::one(), Mul::mul)
        }
    }
    impl<'a, M: Modulus + 'a> Sum<&'a MInt<M>> for MInt<M> {
        #[inline]
        fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::zero(), Add::add)
        }
    }
    impl<'a, M: Modulus + 'a> Product<&'a MInt<M>> for MInt<M> {
        #[inline]
        fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::one(), Mul::mul)
        }
    }
    impl<M: Modulus> fmt::Display for MInt<M> {
        fn fmt<'a>(&self, f: &mut fmt::Formatter<'a>) -> Result<(), fmt::Error> {
            write!(f, "{}", self.x)
        }
    }
    impl<M: Modulus> FromStr for MInt<M> {
        type Err = ParseIntError;
        #[inline]
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            s.parse::<u32>().map(Self::new)
        }
    }
    impl<M: Modulus> IterScan for MInt<M> {
        type Output = Self;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            iter.next()?.parse::<MInt<M>>().ok()
        }
    }
    impl<M: Modulus> Zero for MInt<M> {
        #[inline]
        fn zero() -> Self {
            Self::new_unchecked(0)
        }
    }
    impl<M: Modulus> One for MInt<M> {
        #[inline]
        fn one() -> Self {
            Self::new_unchecked(1)
        }
    }
    macro_rules! mint_ref_binop {
        ($ imp : ident , $ method : ident , $ t : ty ) => {
            impl<M: Modulus> $imp<$t> for &$t {
                type Output = <$t as $imp<$t>>::Output;
                #[inline]
                fn $method(self, other: $t) -> <$t as $imp<$t>>::Output {
                    $imp::$method(*self, other)
                }
            }
            impl<M: Modulus> $imp<&$t> for $t {
                type Output = <$t as $imp<$t>>::Output;
                #[inline]
                fn $method(self, other: &$t) -> <$t as $imp<$t>>::Output {
                    $imp::$method(self, *other)
                }
            }
            impl<M: Modulus> $imp<&$t> for &$t {
                type Output = <$t as $imp<$t>>::Output;
                #[inline]
                fn $method(self, other: &$t) -> <$t as $imp<$t>>::Output {
                    $imp::$method(*self, *other)
                }
            }
        };
    }
    mint_ref_binop!(Add, add, MInt<M>);
    mint_ref_binop!(Sub, sub, MInt<M>);
    mint_ref_binop!(Mul, mul, MInt<M>);
    mint_ref_binop!(Div, div, MInt<M>);
    macro_rules! mint_ref_unop {
        ($ imp : ident , $ method : ident , $ t : ty ) => {
            impl<M: Modulus> $imp for &$t {
                type Output = <$t as $imp>::Output;
                #[inline]
                fn $method(self) -> <$t as $imp>::Output {
                    $imp::$method(*self)
                }
            }
        };
    }
    mint_ref_unop!(Neg, neg, MInt<M>);
    macro_rules! mint_ref_op_assign {
        ($ imp : ident , $ method : ident , $ t : ty , $ fromimp : ident , $ frommethod : ident ) => {
            impl<M: Modulus> $imp<$t> for $t {
                #[inline]
                fn $method(&mut self, rhs: $t) {
                    *self = $fromimp::$frommethod(*self, rhs);
                }
            }
            impl<M: Modulus> $imp<&$t> for $t {
                #[inline]
                fn $method(&mut self, other: &$t) {
                    $imp::$method(self, *other);
                }
            }
        };
    }
    mint_ref_op_assign!(AddAssign, add_assign, MInt<M>, Add, add);
    mint_ref_op_assign!(SubAssign, sub_assign, MInt<M>, Sub, sub);
    mint_ref_op_assign!(MulAssign, mul_assign, MInt<M>, Mul, mul);
    mint_ref_op_assign!(DivAssign, div_assign, MInt<M>, Div, div);
}
#[derive(Clone, Debug)]
pub struct MemorizedFactorial<M: Modulus> {
    pub fact: Vec<MInt<M>>,
    pub inv_fact: Vec<MInt<M>>,
}
impl<M: Modulus> MemorizedFactorial<M> {
    pub fn new(max_n: usize) -> Self {
        let mut fact = vec![MInt::one(); max_n + 1];
        let mut inv_fact = vec![MInt::one(); max_n + 1];
        for i in 2..=max_n {
            fact[i] = fact[i - 1] * MInt::new(i as u32);
        }
        inv_fact[max_n] = fact[max_n].inv();
        for i in (3..=max_n).rev() {
            inv_fact[i - 1] = inv_fact[i] * MInt::new(i as u32);
        }
        Self { fact, inv_fact }
    }
    #[inline]
    pub fn combination(&self, n: usize, r: usize) -> MInt<M> {
        debug_assert!(n < self.fact.len());
        if r <= n {
            self.fact[n] * self.inv_fact[r] * self.inv_fact[n - r]
        } else {
            MInt::zero()
        }
    }
    #[inline]
    pub fn permutation(&self, n: usize, r: usize) -> MInt<M> {
        debug_assert!(n < self.fact.len());
        if r <= n {
            self.fact[n] * self.inv_fact[n - r]
        } else {
            MInt::zero()
        }
    }
    #[inline]
    pub fn homogeneous_product(&self, n: usize, r: usize) -> MInt<M> {
        debug_assert!(n + r < self.fact.len() + 1);
        if n != 0 && r != 0 {
            self.combination(n + r - 1, r)
        } else {
            MInt::one()
        }
    }
    #[inline]
    pub fn inv(&self, n: usize) -> MInt<M> {
        debug_assert!(n < self.fact.len());
        debug_assert!(n > 0);
        self.inv_fact[n] * self.fact[n - 1]
    }
}
pub struct NumberTheoreticTransform<M: Modulus>(std::marker::PhantomData<fn() -> M>);
pub trait NTTModulus: Modulus {
    fn primitive_root() -> u32;
}
mod number_theoretic_transform_impls {
    use super::*;
    impl NTTModulus for modulus::Modulo998244353 {
        fn primitive_root() -> u32 {
            const G: u32 = 3;
            G
        }
    }
    macro_rules! make_ntt_modulus {
        ($ t : ident , $ m : expr , $ g : expr ) => {
            pub struct $t {}
            impl Modulus for $t {
                #[inline]
                fn get_modulus() -> u32 {
                    const MODULUS: u32 = $m;
                    MODULUS
                }
            }
            impl NTTModulus for $t {
                #[inline]
                fn primitive_root() -> u32 {
                    const G: u32 = $g;
                    G
                }
            }
        };
    }
    make_ntt_modulus!(Modulo2113929217, 2_113_929_217, 5);
    make_ntt_modulus!(Modulo1811939329, 1_811_939_329, 13);
    make_ntt_modulus!(Modulo2013265921, 2_013_265_921, 31);
}
pub type NTT998244353 = NumberTheoreticTransform<modulus::Modulo998244353>;
impl<M: NTTModulus> NumberTheoreticTransform<M> {
    pub fn convert<T: Into<MInt<M>>, I: IntoIterator<Item = T>>(iter: I) -> Vec<MInt<M>> {
        iter.into_iter().map(|x| x.into()).collect()
    }
    pub fn ntt(mut f: Vec<MInt<M>>, inv: bool) -> Vec<MInt<M>> {
        let n = f.len();
        debug_assert!(n.count_ones() == 1);
        let q = MInt::<M>::get_mod() as usize - 1;
        debug_assert!(n.trailing_zeros() <= q.trailing_zeros());
        let mask = n - 1;
        let omega = MInt::<M>::new_unchecked(M::primitive_root()).pow(q / n);
        let omega = if inv { omega.inv() } else { omega };
        let mut g = vec![MInt::<M>::zero(); n];
        let mut i = n / 2;
        while i >= 1 {
            let t = omega.pow(i);
            let mut w = MInt::<M>::one();
            for j in (0..n).step_by(i) {
                for k in 0..i {
                    g[j + k] = f[((j * 2) & mask) + k] + w * f[((j * 2 + i) & mask) + k];
                }
                w *= t;
            }
            i /= 2;
            std::mem::swap(&mut f, &mut g);
        }
        if inv {
            let u = MInt::<M>::new(n as u32).inv();
            for a in f.iter_mut() {
                *a *= u;
            }
        }
        f
    }
    pub fn convolve(mut a: Vec<MInt<M>>, mut b: Vec<MInt<M>>) -> Vec<MInt<M>> {
        let m = a.len() + b.len() - 1;
        let n = 1usize << format!("{:b}", m).len();
        a.resize_with(n, MInt::<M>::zero);
        b.resize_with(n, MInt::<M>::zero);
        let a = Self::ntt(a, false);
        let b = Self::ntt(b, false);
        let c: Vec<_> = a
            .into_iter()
            .zip(b.into_iter())
            .map(|(a, b)| a * b)
            .collect();
        let mut c = Self::ntt(c, true);
        c.truncate(m);
        c
    }
    pub fn convolve_it<T: Into<MInt<M>>, I: IntoIterator<Item = T>>(
        iter1: I,
        iter2: I,
    ) -> Vec<MInt<M>> {
        Self::convolve(Self::convert(iter1), Self::convert(iter2))
    }
}
/// max(a.len(), b.len()) * max(a) * max(b) < 3.64 * 10^18
pub fn convolve2(mut a: Vec<u64>, mut b: Vec<u64>) -> Vec<u64> {
    let m = a.len() + b.len() - 1;
    let n = 1usize << format!("{:b}", m).len();
    a.resize_with(n, Default::default);
    b.resize_with(n, Default::default);
    type M1 = number_theoretic_transform_impls::Modulo2013265921;
    type M2 = number_theoretic_transform_impls::Modulo1811939329;
    let c1 = NumberTheoreticTransform::<M1>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let c2 = NumberTheoreticTransform::<M2>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let p1 = M1::get_modulus() as u64;
    let p1_inv = MInt::<M2>::new(M1::get_modulus()).inv();
    c1.into_iter()
        .zip(c2.into_iter())
        .take(m)
        .map(|(c1, c2)| {
            c1.inner() as u64 + p1 * ((c2 - MInt::<M2>::from(c1.inner())) * p1_inv).inner() as u64
        })
        .collect()
}
/// max(a.len(), b.len()) * max(a) * max(b) < 1.81 * 10^27
pub fn convolve3<M: Modulus>(mut a: Vec<u64>, mut b: Vec<u64>) -> Vec<MInt<M>> {
    let m = a.len() + b.len() - 1;
    let n = 1usize << format!("{:b}", m).len();
    a.resize_with(n, Default::default);
    b.resize_with(n, Default::default);
    type M1 = number_theoretic_transform_impls::Modulo2013265921;
    type M2 = number_theoretic_transform_impls::Modulo1811939329;
    type M3 = number_theoretic_transform_impls::Modulo2113929217;
    let c1 = NumberTheoreticTransform::<M1>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let c2 = NumberTheoreticTransform::<M2>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let c3 = NumberTheoreticTransform::<M3>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let t1 = MInt::<M2>::new(M1::get_modulus()).inv();
    let m1 = MInt::<M>::new(M1::get_modulus());
    let m13 = MInt::<M3>::new(M1::get_modulus());
    let t2 = (MInt::<M3>::new(M1::get_modulus()) * MInt::<M3>::new(M2::get_modulus())).inv();
    let m2 = m1 * MInt::<M>::new(M2::get_modulus());
    c1.into_iter()
        .zip(c2.into_iter())
        .zip(c3.into_iter())
        .take(m)
        .map(|((c1, c2), c3)| {
            let x = MInt::<M3>::new(c1.inner())
                + MInt::<M3>::new(((c2 - MInt::<M2>::from(c1.inner())) * t1).inner()) * m13;
            MInt::<M>::new(c1.inner())
                + MInt::<M>::new(((c2 - MInt::<M2>::from(c1.inner())) * t1).inner()) * m1
                + MInt::<M>::new(((c3 - MInt::<M3>::from(x.inner())) * t2).inner()) * m2
        })
        .collect()
}
/// max(a.len(), b.len()) * max(a) * max(b) < 1.81 * 10^27
pub fn convolve3_128(mut a: Vec<u64>, mut b: Vec<u64>) -> Vec<u128> {
    let m = a.len() + b.len() - 1;
    let n = 1usize << format!("{:b}", m).len();
    a.resize_with(n, Default::default);
    b.resize_with(n, Default::default);
    type M1 = number_theoretic_transform_impls::Modulo2013265921;
    type M2 = number_theoretic_transform_impls::Modulo1811939329;
    type M3 = number_theoretic_transform_impls::Modulo2113929217;
    let c1 = NumberTheoreticTransform::<M1>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let c2 = NumberTheoreticTransform::<M2>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let c3 = NumberTheoreticTransform::<M3>::convolve_it(a.iter().cloned(), b.iter().cloned());
    let p1 = M1::get_modulus();
    let t1 = MInt::<M2>::new(p1).inv();
    let m1 = p1 as u64;
    let p2 = M2::get_modulus();
    let t2 = (MInt::<M3>::new(p1) * MInt::<M3>::new(p2)).inv();
    let m2 = m1 as u128 * p2 as u128;
    c1.into_iter()
        .zip(c2.into_iter())
        .zip(c3.into_iter())
        .take(m)
        .map(|((c1, c2), c3)| {
            let x =
                c1.inner() as u64 + ((c2 - MInt::<M2>::from(c1.inner())) * t1).inner() as u64 * m1;
            x as u128 + ((c3 - MInt::<M3>::from(x)) * t2).inner() as u128 * m2
        })
        .collect()
}
type M = modulus::MInt998244353;
type NTT = NTT998244353;
fn main() {
    #![allow(unused_imports, unused_macros)]
    use std::io::{stdin, stdout, BufWriter, Read as _, Write as _};
    let mut _in_buf = Vec::new();
    stdin().read_to_end(&mut _in_buf).expect("io error");
    let _in_buf = unsafe { String::from_utf8_unchecked(_in_buf) };
    let mut scanner = Scanner::new(&_in_buf);
    macro_rules ! scan {() => {scan ! (usize ) } ; (($ ($ t : tt ) ,* ) ) => {($ (scan ! ($ t ) ) ,* ) } ; ([$ t : tt ; $ len : expr ] ) => {(0 ..$ len ) . map (| _ | scan ! ($ t ) ) . collect ::< Vec < _ >> () } ; ([$ t : ty ; $ len : expr ] ) => {scanner . scan_vec ::<$ t > ($ len ) } ; ([$ t : ty ] ) => {scanner . iter ::<$ t > () } ; ({$ e : expr } ) => {scanner . mscan ($ e ) } ; ($ t : ty ) => {scanner . scan ::<$ t > () } ; }
    let _out = stdout();
    let mut _out = BufWriter::new(_out.lock());
    macro_rules ! print {($ ($ arg : tt ) * ) => (:: std :: write ! (_out , $ ($ arg ) * ) . expect ("io error" ) ) }
    macro_rules ! println {($ ($ arg : tt ) * ) => (:: std :: writeln ! (_out , $ ($ arg ) * ) . expect ("io error" ) ) }
    macro_rules! echo {
        ($ iter : expr ) => {
            echo!($iter, '\n')
        };
        ($ iter : expr , $ sep : expr ) => {
            let mut iter = $iter.into_iter();
            if let Some(item) = iter.next() {
                print!("{}", item);
            }
            for item in iter {
                print!("{}{}", $sep, item);
            }
            println!();
        };
    }
    let n = scan!();
    let h = scan!([usize; n * 2]);
    if n == 1 {
        // println!("{}", (h[0] != h[1]) as usize);
        // return;
    }
    let f = MemorizedFactorial::new(n * 2);
    let mut c = vec![0; 100_001];
    for &h in &h {
        c[h] += 1;
    }
    let mut ans = M::zero();
    let mut heap = BinaryHeap::new();
    for i in c.iter().cloned() {
        if i < 2 {
            continue;
        }
        let v: Vec<_> = (0..=i / 2)
            .rev()
            .map(|j| {
                (-M::one()).pow(j) * f.permutation(i, j * 2) * f.inv_fact[j] / M::new(2).pow(j)
            })
            .collect();
        heap.push((Reverse(v.len()), v));
    }
    while heap.len() > 1 {
        let x = heap.pop().unwrap().1;
        let y = heap.pop().unwrap().1;
        let z = NTT::convolve(x, y);
        heap.push((Reverse(z.len()), z));
    }
    let mut v = heap.pop().map(|t| t.1).unwrap_or(vec![M::one()]);
    v.reverse();
    for i in 0..v.len() {
        ans += v[i] * f.permutation(2 * n - 2 * i, n - i) / M::new(2).pow(n - i);
    }
    println!("{}", ans);
}
use std::{cmp::Reverse, collections::BinaryHeap};


Measured memory_bytes: 7288