use factorial::Factorial;
#[allow(unused_imports)]
use ngtio::prelude::*;

use polynomial::Poly;
use std::collections::BinaryHeap;
use type_traits::One;

type Fp = fp::F998244353;

fn g(k: usize, fact: &Factorial<Fp>, pow_2_inv: &[Fp]) -> Poly<Fp> {
    Poly::new(
        (0..)
            .take_while(|&i| 2 * i <= k)
            .map(|i| fact[k] * fact.inv(k - 2 * i) * fact.inv(i) * pow_2_inv[i])
            .collect(),
    )
}

use std::cmp::{Ord, Ordering, Reverse};

#[derive(Debug, Clone, PartialEq, Eq)]
struct Len(Poly<Fp>);
impl Ord for Len {
    fn cmp(&self, rhs: &Self) -> Ordering {
        (self.0).0.len().cmp(&(rhs.0).0.len())
    }
}
impl PartialOrd for Len {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        (self.0).0.len().partial_cmp(&(rhs.0).0.len())
    }
}

fn main() {
    let mut buf = ngtio::with_stdin();
    let n = buf.usize();
    let fact = Factorial::new(2 * n + 1, |x| Fp::new(x as i64));
    let pow_2_inv = std::iter::successors(Some(Fp::one()), |x| Some(x * Fp::new(2).inv()))
        .take(2 * n + 1)
        .collect::<Vec<_>>();
    let mut double_factorial = vec![Fp::one(); 2 * n + 1];
    for i in 2..=2 * n {
        double_factorial[i] = double_factorial[i - 2] * Fp::new(i as i64);
    }

    let mut m = vec![0; 100_000];
    for _ in 0..2 * n {
        let x = buf.parse::<Usize1>();
        m[x] += 1;
    }
    let mut heap = m
        .iter()
        .copied()
        .filter(|&x| 2 <= x)
        .map(|x| g(x, &fact, &pow_2_inv))
        .map(Len)
        .map(Reverse)
        .collect::<BinaryHeap<_>>();
    while 1 < heap.len() {
        let x = (heap.pop().unwrap().0).0;
        let y = (heap.pop().unwrap().0).0;
        heap.push(Reverse(Len(fft::multiply(x, y))));
    }
    let mul = heap.pop().map(|len| (len.0).0).unwrap_or_else(Poly::one);
    assert!(heap.is_empty());
    let ans = mul
        .into_inner()
        .iter()
        .enumerate()
        .map(|(i, &x)| {
            let sign = if i % 2 == 0 { Fp::one() } else { -Fp::one() };
            x * sign * double_factorial[(2 * (n - i)).saturating_sub(1)]
        })
        .sum::<Fp>();
    println!("{}", ans);
}

// dbg {{{
#[allow(dead_code)]
mod dbg {
    #[macro_export]
    macro_rules! lg {
        () => {
            $crate::eprintln!("[{}:{}]", $crate::file!(), $crate::line!());
        };
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}] {} = {:?}",
                        file!(), line!(), stringify!($val), &tmp);
                    tmp
                }
            }
        };
        ($val:expr,) => { $crate::lg!($val) };
        ($($val:expr),+ $(,)?) => {
            ($($crate::lg!($val)),+,)
        };
    }

    #[macro_export]
    macro_rules! lg_nl {
        () => {
            eprintln!("[{}:{}]", $crate::file!(), $crate::line!());
        };
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}] {}:\n{:?}", file!(), line!(), stringify!($val), tmp);
                    tmp
                }
            };
        };
    }

    #[macro_export]
    macro_rules! msg {
        () => {
            compile_error!();
        };
        ($msg:expr) => {
            $crate::eprintln!("[{}:{}][{}]", $crate::file!(), $crate::line!(), $msg);
        };
        ($msg:expr, $val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}][{}] {} = {:?}",
                        file!(), line!(), $msg, stringify!($val), &tmp);
                    tmp
                }
            }
        };
        ($msg:expr, $val:expr,) => { msg!($msg, $val) };
        ($msg:expr, $($val:expr),+ $(,)?) => {
            ($(msg!($msg, $val)),+,)
        };
    }

    #[macro_export]
    macro_rules! tabular {
        ($val:expr) => {
            $crate::lg_nl!(crate::dbg::Tabular($val))
        };
    }

    #[macro_export]
    macro_rules! boolean_table {
        ($val:expr) => {
            $crate::lg_nl!(crate::dbg::BooleanTable($val));
        };
    }

    #[macro_export]
    macro_rules! boolean_slice {
        ($val:expr) => {
            $crate::lg!(crate::dbg::BooleanSlice($val));
        };
    }

    use std::fmt::{Debug, Formatter};

    #[derive(Clone)]
    pub struct Tabular<'a, T: Debug>(pub &'a [T]);
    impl<'a, T: Debug> Debug for Tabular<'a, T> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, &self.0[i])?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanTable<'a>(pub &'a [Vec<bool>]);
    impl<'a> Debug for BooleanTable<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, BooleanSlice(&self.0[i]))?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanSlice<'a>(pub &'a [bool]);
    impl<'a> Debug for BooleanSlice<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            write!(
                f,
                "{}",
                self.0
                    .iter()
                    .map(|&b| if b { "1 " } else { "0 " })
                    .collect::<String>()
            )?;
            Ok(())
        }
    }
}
// }}}
// polynomial {{{
#[allow(dead_code)]
mod polynomial {
    #![warn(missing_docs)]

    use crate::type_traits::{One, Ring, Zero};

    mod arith {
        use super::Poly;
        use crate::type_traits::Ring;
        use std::ops::*;

        impl<T: Ring + Copy> Add for Poly<T> {
            type Output = Poly<T>;
            fn add(self, rhs: Self) -> Self::Output {
                let mut res = self.0.clone();
                if self.0.len() < rhs.0.len() {
                    res.resize(rhs.0.len(), T::zero());
                }
                res.iter_mut().zip(rhs.0.iter()).for_each(|(x, y)| {
                    *x += *y;
                });
                Self::remove_trailig_zeros(&mut res);
                Poly(res)
            }
        }

        impl<T: Ring + Copy> Sub for Poly<T>
        where
            T: Sub + SubAssign,
        {
            type Output = Poly<T>;
            fn sub(self, rhs: Self) -> Self::Output {
                let mut res = self.0.clone();
                if self.0.len() < rhs.0.len() {
                    res.resize(rhs.0.len(), T::zero());
                }
                res.iter_mut().zip(rhs.0.iter()).for_each(|(x, y)| {
                    *x -= *y;
                });
                Self::remove_trailig_zeros(&mut res);
                Poly(res)
            }
        }

        #[allow(clippy::suspicious_arithmetic_impl)]
        impl<T: Ring + Copy> Mul for Poly<T> {
            type Output = Poly<T>;
            fn mul(self, rhs: Self) -> Self::Output {
                if self.0.is_empty() && rhs.0.is_empty() {
                    Poly(Vec::new())
                } else {
                    let mut res = vec![T::zero(); self.0.len() + rhs.0.len() - 1];
                    for (i, &x) in self.0.iter().enumerate() {
                        for (j, &y) in rhs.0.iter().enumerate() {
                            res[i + j] += x * y;
                        }
                    }
                    Self::remove_trailig_zeros(&mut res);
                    Poly(res)
                }
            }
        }

        // TODO: このマクロを fp のものと共通化します。
        macro_rules! forward_assign_biop {
            ($(impl $trait:ident, $fn_assign:ident, $fn:ident)*) => {
                $(
                    impl<T: Ring + Copy> $trait for Poly<T> {
                        #[inline]
                        fn $fn_assign(&mut self, rhs: Self) {
                            *self = self.clone().$fn(&rhs);
                        }
                    }
                )*
            };
        }
        forward_assign_biop! {
            impl AddAssign, add_assign, add
            impl SubAssign, sub_assign, sub
            impl MulAssign, mul_assign, mul
        }

        // TODO: このマクロを fp のものと共通化します。
        macro_rules! forward_ref_binop {
            ($(impl $imp:ident, $method:ident)*) => {
                $(
                    impl<'a, T: Ring + Ring + Copy> $imp<Poly<T>> for &'a Poly<T> {
                        type Output = Poly<T>;
                        #[inline]
                        fn $method(self, other: Poly<T>) -> Self::Output {
                            $imp::$method(self.clone(), other.clone())
                        }
                    }

                    impl<'a, T: Ring + Copy> $imp<&'a Poly<T>> for Poly<T> {
                        type Output = Poly<T>;
                        #[inline]
                        fn $method(self, other: &Poly<T>) -> Self::Output {
                            $imp::$method(self.clone(), other.clone())
                        }
                    }

                    impl<'a, T: Ring + Copy> $imp<&'a Poly<T>> for &'a Poly<T> {
                        type Output = Poly<T>;
                        #[inline]
                        fn $method(self, other: &Poly<T>) -> Self::Output {
                            $imp::$method(self.clone(), other)
                        }
                    }
                )*
            };
        }
        forward_ref_binop! {
            impl Add, add
            impl Sub, sub
            impl Mul, mul
        }
    }

    #[derive(Debug, Clone, PartialEq, Eq)]
    pub struct Poly<T>(pub Vec<T>);

    impl<T: Ring + Copy> Poly<T> {
        pub fn new(mut src: Vec<T>) -> Self {
            Poly::remove_trailig_zeros(&mut src);
            Poly(src)
        }

        pub fn into_inner(self) -> Vec<T> {
            self.0
        }

        pub fn pow(mut self, mut b: u64) -> Poly<T> {
            let mut res = Poly::one();
            while b != 0 {
                if b % 2 == 1 {
                    res *= self.clone();
                }
                self *= self.clone();
                b /= 2
            }
            res
        }

        fn remove_trailig_zeros(a: &mut Vec<T>) {
            while a.last().map(T::is_zero).unwrap_or(false) {
                a.pop();
            }
        }
    }

    impl<T: Ring + Copy> Default for Poly<T> {
        fn default() -> Poly<T> {
            Poly(Vec::new())
        }
    }

    impl<T: Ring + Copy> Zero for Poly<T> {
        fn zero() -> Poly<T> {
            Poly(Vec::new())
        }
    }

    impl<T: Ring + Copy> One for Poly<T> {
        fn one() -> Poly<T> {
            Poly(vec![T::one()])
        }
    }
}
// }}}
// factorial {{{
#[allow(dead_code)]
mod factorial {
    use std::{fmt, iter, ops, slice};

    #[derive(Debug, Clone)]
    pub struct Factorial<T> {
        table: Vec<T>,
        inverse: Vec<T>,
    }

    impl<T> Factorial<T>
    where
        T: Clone + fmt::Debug + ops::Mul<Output = T> + ops::Div<Output = T>,
    {
        pub fn new(len: usize, from_usize: impl Fn(usize) -> T) -> Self {
            if len == 0 {
                Self {
                    table: Vec::new(),
                    inverse: Vec::new(),
                }
            } else {
                let mut table = vec![from_usize(1); len];
                for i in 1..len {
                    table[i] = table[i - 1].clone() * from_usize(i);
                }
                let mut inverse = vec![from_usize(1); len];
                inverse[len - 1] = from_usize(1) / table[len - 1].clone();
                for i in (1..len).rev() {
                    inverse[i - 1] = inverse[i].clone() * from_usize(i);
                }
                Self { table, inverse }
            }
        }

        pub fn inv(&self, i: usize) -> T {
            self.inverse[i].clone()
        }

        pub fn falling(&self, n: usize, k: usize) -> T {
            assert!(k <= n, "未対応です。0 がほしいでしょうか。");
            assert!(n < self.table.len(), "ちわーす。範囲外でーすｗｗｗ");
            self[n].clone() * self.inv(k)
        }

        pub fn binom(&self, n: usize, k: usize) -> T {
            assert!(k <= n, "未対応です。0 がほしいでしょうか。");
            assert!(n < self.table.len(), "ちわーす。範囲外でーすｗｗｗ");
            self[n].clone() * self.inv(k) * self.inv(n - k)
        }

        pub fn multichoose(&self, n: usize, k: usize) -> T {
            self.binom(n + k - 1, k - 1)
        }

        pub fn multinom(&self, a: &[usize]) -> T
        where
            T: iter::Product<T>,
        {
            let n = a.iter().sum::<usize>();
            assert!(n < self.table.len(), "ちわーす。範囲外でーすｗｗｗ");
            self[n].clone() * a.iter().map(|&x| self.inv(x)).product::<T>()
        }
    }

    impl<T, I> ops::Index<I> for Factorial<T>
    where
        I: slice::SliceIndex<[T]>,
    {
        type Output = I::Output;

        #[inline]
        fn index(&self, index: I) -> &I::Output {
            &self.table[index]
        }
    }
}
// }}}
// fp {{{
#[allow(dead_code)]
mod fp {
    #![warn(missing_docs)]
    use crate::type_traits::*;
    pub use aliases::*;
    use std::{cmp, fmt, iter, mem, ops::*};

    mod arith {
        use super::{Fp, Modable, Value};
        use crate::type_traits::*;
        use std::ops::*;

        impl<Mod: Modable> Add for Fp<Mod>
        where
            Mod::Output: Value,
        {
            type Output = Self;

            #[inline]
            fn add(self, rhs: Self) -> Self {
                Self(Self::normalize_from_the_bottom(
                    self.into_inner() + rhs.into_inner(),
                ))
            }
        }

        impl<Mod: Modable> Sub for Fp<Mod>
        where
            Mod::Output: Value,
        {
            type Output = Self;

            #[inline]
            fn sub(self, rhs: Self) -> Self {
                Self(Self::normalize_from_the_top(
                    self.into_inner() - rhs.into_inner(),
                ))
            }
        }

        impl<Mod: Modable> Mul for Fp<Mod>
        where
            Mod::Output: Value,
        {
            type Output = Self;

            #[inline]
            fn mul(self, rhs: Self) -> Self {
                Self::new(self.into_inner() * rhs.into_inner())
            }
        }

        #[allow(clippy::suspicious_arithmetic_impl)]
        impl<Mod: Modable> Div for Fp<Mod>
        where
            Mod::Output: Value,
        {
            type Output = Self;

            #[inline]
            fn div(self, rhs: Self) -> Self {
                self * rhs.inv()
            }
        }

        impl<Mod: Modable> Neg for Fp<Mod>
        where
            Mod::Output: Value,
        {
            type Output = Self;

            #[inline]
            fn neg(self) -> Self {
                if self.into_inner().is_zero() {
                    Self::zero()
                } else {
                    Self(Mod::VALUE - self.into_inner())
                }
            }
        }

        impl<Mod: Modable> Neg for &Fp<Mod>
        where
            Mod::Output: Value,
        {
            type Output = Fp<Mod>;

            #[inline]
            fn neg(self) -> Fp<Mod> {
                if self.into_inner().is_zero() {
                    Fp::zero()
                } else {
                    Fp(Mod::VALUE - self.into_inner())
                }
            }
        }

        macro_rules! forward_assign_biop {
            ($(impl $trait:ident, $fn_assign:ident, $fn:ident)*) => {
                $(
                    impl<Mod: Modable> $trait for Fp<Mod>
                    where
                        Mod::Output: Value
                    {
                        #[inline]
                        fn $fn_assign(&mut self, rhs: Self) {
                            *self = self.$fn(rhs);
                        }
                    }
                )*
            };
        }
        forward_assign_biop! {
            impl AddAssign, add_assign, add
            impl SubAssign, sub_assign, sub
            impl MulAssign, mul_assign, mul
            impl DivAssign, div_assign, div
        }

        macro_rules! forward_ref_binop {
            ($(impl $imp:ident, $method:ident)*) => {
                $(
                    impl<'a, Mod: Modable> $imp<Fp<Mod>> for &'a Fp<Mod>
                    where
                        Mod::Output:Value
                    {
                        type Output = Fp<Mod>;

                        #[inline]
                        fn $method(self, other: Fp<Mod>) -> Self::Output {
                            $imp::$method(*self, other)
                        }
                    }

                    impl<'a, Mod: Modable> $imp<&'a Fp<Mod>> for Fp<Mod>
                    where
                        Mod::Output:Value
                    {
                        type Output = Fp<Mod>;

                        #[inline]
                        fn $method(self, other: &Fp<Mod>) -> Self::Output {
                            $imp::$method(self, *other)
                        }
                    }

                    impl<'a, Mod: Modable> $imp<&'a Fp<Mod>> for &'a Fp<Mod>
                    where
                        Mod::Output:Value
                    {
                        type Output = Fp<Mod>;

                        #[inline]
                        fn $method(self, other: &Fp<Mod>) -> Self::Output {
                            $imp::$method(*self, *other)
                        }
                    }
                )*
            };
        }
        forward_ref_binop! {
            impl Add, add
            impl Sub, sub
            impl Mul, mul
            impl Div, div
        }
    }

    #[macro_export]
    macro_rules! fp_vec {
        () => (
            Vec::<$crate::Fp<_>>::new()
        );
        ($elem:expr; $n:expr) => (
            vec![$crate::Fp::new($elem); $n]
        );
        ($($x:expr),+ $(,)?) => (
            vec![$($crate::Fp::new($x),)+];
        );
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    pub struct Fp<Mod: Modable>(Mod::Output);

    impl<Mod: Modable> Fp<Mod>
    where
        Mod::Output: Value,
    {
        #[inline]
        pub fn new(src: Mod::Output) -> Self {
            Self(Self::normalize(src))
        }

        #[inline]
        pub fn frac(num: Mod::Output, den: Mod::Output) -> Self {
            Self::new(num) / Self::new(den)
        }

        #[inline]
        pub fn into_inner(self) -> Mod::Output {
            self.0
        }

        #[allow(clippy::many_single_char_names)]
        pub fn inv(self) -> Self {
            assert_ne!(
                self.into_inner(),
                Mod::Output::zero(),
                "さては 0 の逆元を取ろうとしていますね？"
            );
            let mut x = self.into_inner();
            let mut y = Mod::VALUE;
            let mut u = Mod::Output::one();
            let mut v = Mod::Output::zero();
            while x != Mod::Output::zero() {
                let q = y / x;
                y -= q * x;
                v -= q * u;
                mem::swap(&mut x, &mut y);
                mem::swap(&mut u, &mut v);
            }
            assert!(
                x == Mod::Output::zero()
                    && y == Mod::Output::one()
                    && (u == Mod::VALUE || u == -Mod::VALUE)
                    && (-Mod::VALUE < v && v < Mod::VALUE)
            );
            Self(Self::normalize_from_the_top(v))
        }

        pub fn pow(mut self, mut p: u64) -> Self {
            let mut ans = Self::one();
            while p != 0 {
                if p % 2 == 1 {
                    ans *= self;
                }
                self *= self;
                p /= 2;
            }
            ans
        }

        #[inline]
        fn normalize(src: Mod::Output) -> Mod::Output {
            Self::normalize_from_the_top(src % Mod::VALUE)
        }

        #[inline]
        fn normalize_from_the_bottom(src: Mod::Output) -> Mod::Output {
            if Mod::VALUE <= src {
                src - Mod::VALUE
            } else {
                src
            }
        }

        #[inline]
        fn normalize_from_the_top(src: Mod::Output) -> Mod::Output {
            if src < Mod::Output::zero() {
                src + Mod::VALUE
            } else {
                src
            }
        }
    }

    impl<Mod: Modable> Zero for Fp<Mod>
    where
        Mod::Output: Value,
    {
        #[inline]
        fn zero() -> Fp<Mod> {
            Fp::new(Mod::Output::zero())
        }
    }

    impl<Mod: Modable> One for Fp<Mod>
    where
        Mod::Output: Value,
    {
        #[inline]
        fn one() -> Fp<Mod> {
            Fp::new(Mod::Output::one())
        }
    }

    impl<Mod: Modable> iter::Sum<Fp<Mod>> for Fp<Mod>
    where
        Mod::Output: Value,
    {
        fn sum<I>(iter: I) -> Self
        where
            I: iter::Iterator<Item = Fp<Mod>>,
        {
            iter.fold(Fp::zero(), Add::add)
        }
    }

    impl<'a, Mod: 'a + Modable> iter::Sum<&'a Fp<Mod>> for Fp<Mod>
    where
        Mod::Output: Value,
    {
        fn sum<I>(iter: I) -> Self
        where
            I: iter::Iterator<Item = &'a Fp<Mod>>,
        {
            iter.fold(Fp::zero(), Add::add)
        }
    }

    impl<Mod: Modable> iter::Product<Fp<Mod>> for Fp<Mod>
    where
        Mod::Output: Value,
    {
        fn product<I>(iter: I) -> Self
        where
            I: iter::Iterator<Item = Fp<Mod>>,
        {
            iter.fold(Self::one(), Mul::mul)
        }
    }

    impl<'a, Mod: 'a + Modable> iter::Product<&'a Fp<Mod>> for Fp<Mod>
    where
        Mod::Output: Value,
    {
        fn product<I>(iter: I) -> Self
        where
            I: iter::Iterator<Item = &'a Fp<Mod>>,
        {
            iter.fold(Self::one(), Mul::mul)
        }
    }

    impl<Mod: Modable> fmt::Display for Fp<Mod>
    where
        Mod::Output: Value,
    {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
            write!(f, "{}", self.0)
        }
    }

    pub trait Modable: Constant + Clone + fmt::Debug + cmp::PartialEq + cmp::Eq {}
    impl<Mod: Constant + Clone + fmt::Debug + cmp::PartialEq + cmp::Eq> Modable for Mod {}

    pub trait Value:
        Sized
        + Clone
        + Copy
        + Ring
        + fmt::Debug
        + fmt::Display
        + cmp::PartialOrd
        + cmp::Ord
        + cmp::Eq
        + Div<Output = Self>
        + Rem<Output = Self>
        + Neg<Output = Self>
        + DivAssign
        + RemAssign
    {
    }

    macro_rules! impl_value {
        ($($type:ty,)*) => { $(impl Value for $type {})* };
    }

    impl_value! { i8, i16, i32, i64, i128, isize, }

    mod aliases {
        use super::Fp;
        use crate::type_traits::Constant;

        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub struct Mod1000000007 {}
        pub type F1000000007 = Fp<Mod1000000007>;
        impl Constant for Mod1000000007 {
            type Output = i64;
            const VALUE: i64 = 1_000_000_007;
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub struct Mod998244353 {}
        pub type F998244353 = Fp<Mod998244353>;
        impl Constant for Mod998244353 {
            type Output = i64;
            const VALUE: i64 = 998_244_353;
        }
    }
}
// }}}
// type_traits {{{
#[allow(dead_code)]
mod type_traits {
    #![warn(missing_docs)]

    use std::{cmp, fmt, ops};

    mod primitive {
        use super::{
            binary::{Add, Mul},
            Commut, One, OpN, Zero,
        };

        macro_rules! zero {
            (int) => {
                0
            };
            (float) => {
                0.
            };
        }
        macro_rules! one {
            (int) => {
                1
            };
            (float) => {
                1.
            };
        }
        macro_rules! num {
            (@kind $kind:ident @type $T:ty) => {
                impl Zero for $T {
                    fn zero() -> $T {
                        zero!($kind)
                    }
                }
                impl One for $T {
                    fn one() -> $T {
                        one!($kind)
                    }
                }
                impl Commut for Add<$T> {}
                impl OpN for Add<$T> {
                    fn op_n(self, n: u64) -> Self {
                        Add(self.0 * n as $T)
                    }
                }
                impl Commut for Mul<$T> {}
            };
        }

        macro_rules! int {
            ($($T:ty,)*) => {
                $( num! { @kind int @type $T } )*
            };
        }

        macro_rules! float {
            ($($T:ty,)*) => {
                $( num! { @kind float @type $T } )*
            };
        }

        int! {
            u8, u16, u32, u64, u128, usize,
            i8, i16, i32, i64, i128, isize,
        }

        float! {
            f32, f64,
        }
    }

    pub mod binary {
        use super::{Assoc, Commut, Element, Identity, One, OpN, Peek, Zero};
        use std::ops;

        macro_rules! triv_wrapper {
            ($name:ident<$T:ident>) => {
                impl<$T> Peek for $name<$T>
                where
                    $T: Element,
                {
                    type Inner = $T;
                    fn peek(&self) -> $T {
                        self.0.clone()
                    }
                }
            };
        }

        #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
        pub struct Len<T> {
            pub len: u64,
            pub base: T,
        }
        impl<T> Len<T> {
            pub fn single(base: T) -> Self {
                Len { len: 1, base }
            }
        }
        impl<T: Assoc> Assoc for Len<T> {
            fn op(self, rhs: Self) -> Self {
                Len {
                    len: self.len + rhs.len,
                    base: self.base.op(rhs.base),
                }
            }
        }

        #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
        pub struct Pair<T, U>(pub T, pub U);
        impl<T: Assoc, U: Assoc> Assoc for Pair<T, U> {
            fn op(self, rhs: Self) -> Self {
                Pair(self.0.op(rhs.0), self.1.op(rhs.1))
            }
        }
        impl<T: Identity, U: Identity> Identity for Pair<T, U> {
            fn identity() -> Self {
                Pair(T::identity(), U::identity())
            }
        }
        impl<T: Commut, U: Commut> Commut for Pair<T, U> {}
        impl<T: OpN, U: OpN> OpN for Pair<T, U> {
            fn op_n(self, n: u64) -> Self {
                let Pair(t, u) = self;
                Self(t.op_n(n), u.op_n(n))
            }
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
        pub struct BitXor<T>(pub T);
        triv_wrapper! { BitXor<T> }
        impl<T> Assoc for BitXor<T>
        where
            T: ops::BitXor<Output = T> + Element,
        {
            fn op(self, rhs: Self) -> Self {
                BitXor(self.0 ^ rhs.0)
            }
        }
        impl<T> Identity for BitXor<T>
        where
            T: ops::BitXor<Output = T> + Zero,
        {
            fn identity() -> Self {
                BitXor(T::zero())
            }
        }
        impl<T: ops::BitXor<Output = T> + Element> Commut for BitXor<T> {}
        impl<T: ops::BitXor<Output = T> + Zero> OpN for BitXor<T> {
            fn op_n(self, n: u64) -> Self {
                if n % 2 == 0 {
                    Self::identity()
                } else {
                    self
                }
            }
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
        pub struct Add<T>(pub T);
        triv_wrapper! { Add<T> }
        impl<T> Assoc for Add<T>
        where
            T: ops::Add<Output = T> + Element,
        {
            fn op(self, rhs: Self) -> Self {
                Add(self.0 + rhs.0)
            }
        }
        impl<T> Identity for Add<T>
        where
            T: Zero,
        {
            fn identity() -> Self {
                Add(T::zero())
            }
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
        pub struct Mul<T>(pub T);
        triv_wrapper! { Mul<T> }
        impl<T> Assoc for Mul<T>
        where
            T: ops::Mul<Output = T> + Element,
        {
            fn op(self, rhs: Self) -> Self {
                Mul(self.0 * rhs.0)
            }
        }
        impl<T> Identity for Mul<T>
        where
            T: One,
        {
            fn identity() -> Self {
                Mul(T::one())
            }
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
        pub struct InvertionNumber {
            pub zero: u64,
            pub one: u64,
            pub invertion: u64,
        }
        impl Peek for InvertionNumber {
            type Inner = bool;
            fn peek(&self) -> bool {
                self.try_get_bool()
                    .expect("ビットでないものを peek するのはいけません！")
            }
        }

        impl Assoc for InvertionNumber {
            fn op(self, rhs: Self) -> Self {
                InvertionNumber {
                    zero: self.zero + rhs.zero,
                    one: self.one + rhs.one,
                    invertion: self.invertion + self.one * rhs.zero + rhs.invertion,
                }
            }
        }
        impl Identity for InvertionNumber {
            fn identity() -> Self {
                InvertionNumber::new()
            }
        }
        impl InvertionNumber {
            pub fn new() -> Self {
                InvertionNumber {
                    zero: 0,
                    one: 0,
                    invertion: 0,
                }
            }
            pub fn try_get_u8(&self) -> Option<u8> {
                self.try_get_bool().map(|b| if b { 1 } else { 0 })
            }
            pub fn try_get_bool(&self) -> Option<bool> {
                if *self == Self::bit_zero() {
                    Some(false)
                } else if *self == Self::bit_one() {
                    Some(true)
                } else {
                    None
                }
            }
            pub fn count_zeros(&self) -> u64 {
                self.zero
            }
            pub fn count_ones(&self) -> u64 {
                self.one
            }
            pub fn inversion_number(&self) -> u64 {
                self.invertion
            }
            pub fn bit_zero() -> Self {
                InvertionNumber {
                    zero: 1,
                    one: 0,
                    invertion: 0,
                }
            }
            pub fn bit_one() -> Self {
                InvertionNumber {
                    zero: 0,
                    one: 1,
                    invertion: 0,
                }
            }
            pub fn from_bool(b: bool) -> Self {
                if b {
                    Self::bit_one()
                } else {
                    Self::bit_zero()
                }
            }
            pub fn from_u8(x: u8) -> Self {
                match x {
                    0 => Self::bit_zero(),
                    1 => Self::bit_one(),
                    _ => panic!("0 でも 1 でもないものを渡すとパニックです。"),
                }
            }
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub struct Affine<T> {
            pub a: T,
            pub b: T,
        }
        impl<T: Element> Peek for Affine<T> {
            type Inner = (T, T);
            fn peek(&self) -> (T, T) {
                (self.a.clone(), self.b.clone())
            }
        }
        impl<T> Assoc for Affine<T>
        where
            T: ops::Add<Output = T> + Element,
            T: ops::Mul<Output = T> + Element,
        {
            fn op(self, rhs: Self) -> Self {
                Self {
                    a: self.a.clone() * rhs.a,
                    b: self.b + self.a * rhs.b,
                }
            }
        }
        impl<T> Identity for Affine<T>
        where
            T: Zero + One,
        {
            fn identity() -> Self {
                Self {
                    a: T::one(),
                    b: T::zero(),
                }
            }
        }

        #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
        pub struct Cat(pub String);
        impl Peek for Cat {
            type Inner = String;
            fn peek(&self) -> String {
                self.0.clone()
            }
        }
        impl Assoc for Cat {
            fn op(self, rhs: Self) -> Self {
                Cat(self.0.chars().chain(rhs.0.chars()).collect())
            }
        }
        impl Identity for Cat {
            fn identity() -> Self {
                Cat(String::new())
            }
        }
    }

    pub mod actions {
        use super::{binary::Len, Action, Commut, OpN};

        #[derive(Debug, Clone, PartialEq, Copy)]
        pub struct Update<T>(pub T);

        impl<T: OpN> Action for Update<T> {
            type Space = Len<T>;
            fn acted(self, x: Self::Space) -> Self::Space {
                Len {
                    len: x.len,
                    base: self.0.op_n(x.len),
                }
            }
        }

        #[derive(Debug, Clone, PartialEq, Copy)]
        pub struct Adjoint<T>(pub T);

        impl<T: OpN + Commut> Action for Adjoint<T> {
            type Space = Len<T>;
            fn acted(self, x: Self::Space) -> Self::Space {
                Len {
                    len: x.len,
                    base: self.0.op_n(x.len).op(x.base),
                }
            }
        }
    }

    pub trait Element: Sized + Clone + PartialEq + fmt::Debug {}
    impl<T: Sized + Clone + PartialEq + fmt::Debug> Element for T {}

    pub trait Assoc: Element {
        fn op(self, rhs: Self) -> Self;

        fn op_from_left(&mut self, left: &Self) {
            *self = Self::op(left.clone(), self.clone());
        }

        fn op_from_right(&mut self, right: &Self) {
            *self = Self::op(self.clone(), right.clone());
        }
    }

    pub trait Identity: Assoc {
        fn identity() -> Self;
    }

    pub trait Commut: Assoc {}

    pub trait OpN: Assoc {
        fn op_n(self, n: u64) -> Self;
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Grade<T> {
        pub base: T,
        pub deg: usize,
    }
    impl<T: Assoc> Assoc for Grade<T> {
        fn op(self, rhs: Self) -> Self {
            Grade {
                deg: self.deg + rhs.deg,
                base: self.base.op(rhs.base),
            }
        }
    }

    pub trait Action {
        type Space: Assoc;
        fn acted(self, x: Self::Space) -> Self::Space;
    }

    pub trait Zero: ops::Add<Output = Self> + ops::AddAssign + Element {
        fn zero() -> Self;

        fn is_zero(&self) -> bool
        where
            Self: cmp::PartialEq,
        {
            self == &Self::zero()
        }
    }

    pub trait One: ops::Mul<Output = Self> + ops::MulAssign + Element {
        fn one() -> Self;

        fn is_one(&self) -> bool
        where
            Self: cmp::PartialEq,
        {
            self == &Self::one()
        }
    }

    pub trait Ring: Zero + One + ops::Neg + ops::Sub<Output = Self> + ops::SubAssign {}
    impl<T: Zero + One + ops::Neg + ops::Sub<Output = Self> + ops::SubAssign> Ring for T {}

    #[macro_export]
    macro_rules! define_constant {
        ($(#[$attr:meta])? $vis:vis type $wrapper_type:ident: $value_type:ty = $value:expr;) => {
            $(#[$attr])?
            #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
            $vis struct $wrapper_type {}

            impl Constant for $wrapper_type {
                type Output = $value_type;
                const VALUE: Self::Output = $value;
            }
        };
    }

    pub trait Peek {
        type Inner: fmt::Debug;

        fn peek(&self) -> Self::Inner;
    }

    pub trait Constant: Copy {
        type Output: Copy;

        const VALUE: Self::Output;
    }
}
// }}}
// fft {{{
#[allow(dead_code)]
mod fft {
    #![warn(missing_docs)]

    use crate::polynomial::Poly;
    use crate::type_traits::Ring;
    use std::{iter, marker};

    mod fftable {
        use super::Fftable;
        use crate::fp::F998244353;

        impl Fftable for F998244353 {
            fn root() -> F998244353 {
                F998244353::new(3).pow(7 * 17)
            }
            fn root_inv() -> F998244353 {
                F998244353::root().inv()
            }
            fn lg_ord() -> usize {
                23
            }
            fn div_assign_by_usize(&mut self, den: usize) {
                *self /= F998244353::new(den as i64)
            }
        }
    }

    pub trait Fftable: Ring + Copy {
        fn root() -> Self;

        fn root_inv() -> Self;

        fn lg_ord() -> usize;

        fn div_assign_by_usize(&mut self, den: usize);

        fn root_seq<Tag: DirectionTag>() -> Vec<Self> {
            let mut root = Tag::root::<Self>();
            let mut res = Vec::with_capacity(Self::lg_ord());
            for _ in 0..Self::lg_ord() {
                res.push(root);
                root *= root;
            }
            res.push(root);
            res.reverse();
            res
        }
    }

    #[must_use]
    pub fn multiply<T>(a: Poly<T>, b: Poly<T>) -> Poly<T>
    where
        T: Fftable + std::fmt::Debug,
    {
        let mut a = a.into_inner();
        let mut b = b.into_inner();
        let n = (a.len() + b.len()).next_power_of_two();
        a.resize(n, T::zero());
        b.resize(n, T::zero());
        a = fft(&a, marker::PhantomData::<Forward>);
        b = fft(&b, marker::PhantomData::<Forward>);
        let mut c = a
            .iter()
            .copied()
            .zip(b.iter().copied())
            .map(|(x, y)| x * y)
            .collect::<Vec<_>>();
        c = fft(&c, marker::PhantomData::<Backward>);
        c.iter_mut().for_each(|x| x.div_assign_by_usize(n));
        Poly::new(c)
    }

    #[allow(clippy::many_single_char_names)]
    #[must_use]
    pub fn fft<T, Tag>(a: &[T], _tag: marker::PhantomData<Tag>) -> Vec<T>
    where
        T: Fftable + std::fmt::Debug,
        Tag: DirectionTag,
    {
        let n = a.len();
        assert!(n.is_power_of_two());
        let mut a = bit_reverse(a);
        for (d, &root) in iter::successors(Some(1), |x| Some(x * 2))
            .take_while(|&d| d != n)
            .zip(T::root_seq::<Tag>()[1..].iter())
        {
            for (i, coeff) in iter::successors(Some((0, T::one())), |&(mut i, mut coeff)| {
                i += 1;
                coeff *= root;
                if i % d == 0 {
                    i += d;
                    coeff = T::one();
                }
                Some((i, coeff))
            })
            .take_while(|&(i, _)| i != n)
            {
                let x = a[i];
                let y = a[i + d];
                a[i] = x + y * coeff;
                a[i + d] = x - y * coeff;
            }
        }
        a
    }

    pub trait DirectionTag {
        fn root<T: Fftable>() -> T;
    }
    pub struct Forward {}
    impl DirectionTag for Forward {
        fn root<T: Fftable>() -> T {
            T::root()
        }
    }
    pub struct Backward {}
    impl DirectionTag for Backward {
        fn root<T: Fftable>() -> T {
            T::root_inv()
        }
    }

    #[must_use]
    fn bit_reverse<T: Copy>(a: &[T]) -> Vec<T> {
        assert!(a.len().is_power_of_two());
        let shift = std::mem::size_of::<usize>() as u32 * 8 - a.len().trailing_zeros();
        (0..a.len())
            .map(|i| a[if i == 0 { 0 } else { i.reverse_bits() >> shift }])
            .collect()
    }
}
// }}}
// ngtio {{{
#[allow(dead_code)]
mod ngtio {
    #![warn(missing_docs)]

    mod i {
        use std::{
            io::{self, BufRead},
            iter,
        };

        pub use multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen};
        pub use token::{Token, Usize1};

        pub fn with_stdin() -> Tokenizer<io::BufReader<io::Stdin>> {
            io::BufReader::new(io::stdin()).tokenizer()
        }

        pub fn with_str(src: &str) -> Tokenizer<&[u8]> {
            src.as_bytes().tokenizer()
        }

        pub struct Tokenizer<S: BufRead> {
            queue: Vec<String>, // FIXME: String のみにすると速そうです。
            scanner: S,
        }
        macro_rules! prim_method {
            ($name:ident: $T:ty) => {
#[allow(missing_docs)]
                pub fn $name(&mut self) -> $T {
                    <$T>::leaf().parse(self)
                }
            };
            ($name:ident) => {
                prim_method!($name: $name);
            };
        }
        macro_rules! prim_methods {
            ($name:ident: $T:ty; $($rest:tt)*) => {
                prim_method!($name:$T);
                prim_methods!($($rest)*);
            };
            ($name:ident; $($rest:tt)*) => {
                prim_method!($name);
                prim_methods!($($rest)*);
            };
            () => ()
        }
        impl<S: BufRead> Tokenizer<S> {
            pub fn token(&mut self) -> String {
                self.load();
                self.queue.pop().expect("入力が終了したのですが。")
            }
            pub fn new(scanner: S) -> Self {
                Self {
                    queue: Vec::new(),
                    scanner,
                }
            }
            fn load(&mut self) {
                while self.queue.is_empty() {
                    let mut s = String::new();
                    let length = self.scanner.read_line(&mut s).unwrap(); // 入力が UTF-8 でないときにエラーだそうです。
                    if length == 0 {
                        break;
                    }
                    self.queue = s.split_whitespace().rev().map(str::to_owned).collect();
                }
            }

            pub fn skip_line(&mut self) {
                assert!(
                    self.queue.is_empty(),
                    "行の途中で呼ばないでいただきたいです。現在のトークンキュー: {:?}",
                    &self.queue
                );
                self.load();
            }

            pub fn end(&mut self) {
                self.load();
                assert!(self.queue.is_empty(), "入力はまだあります！");
            }

            pub fn parse<T: Token>(&mut self) -> T::Output {
                T::parse(&self.token())
            }

            pub fn parse_collect<T: Token, B>(&mut self, n: usize) -> B
            where
                B: iter::FromIterator<T::Output>,
            {
                iter::repeat_with(|| self.parse::<T>()).take(n).collect()
            }

            pub fn tuple<T: RawTuple>(&mut self) -> <T::LeafTuple as Parser>::Output {
                T::leaf_tuple().parse(self)
            }

            pub fn vec<T: Token>(&mut self, len: usize) -> Vec<T::Output> {
                T::leaf().vec(len).parse(self)
            }

            pub fn vec_tuple<T: RawTuple>(
                &mut self,
                len: usize,
            ) -> Vec<<T::LeafTuple as Parser>::Output> {
                T::leaf_tuple().vec(len).parse(self)
            }

            pub fn vec2<T: Token>(&mut self, height: usize, width: usize) -> Vec<Vec<T::Output>> {
                T::leaf().vec(width).vec(height).parse(self)
            }

            pub fn vec2_tuple<T>(
                &mut self,
                height: usize,
                width: usize,
            ) -> Vec<Vec<<T::LeafTuple as Parser>::Output>>
            where
                T: RawTuple,
            {
                T::leaf_tuple().vec(width).vec(height).parse(self)
            }
            prim_methods! {
                u8; u16; u32; u64; u128; usize;
                i8; i16; i32; i64; i128; isize;
                char; string: String;
            }
        }

        mod token {
            use super::multi_token::Leaf;
            use std::{any, fmt, marker, str};

            pub trait Token: Sized {
                type Output;
                fn parse(s: &str) -> Self::Output;
                fn leaf() -> Leaf<Self> {
                    Leaf(marker::PhantomData)
                }
            }

            impl<T> Token for T
            where
                T: str::FromStr,
                <T as str::FromStr>::Err: fmt::Debug,
            {
                type Output = T;
                fn parse(s: &str) -> Self::Output {
                    s.parse().unwrap_or_else(|_| {
                        panic!("Parse error!: ({}: {})", s, any::type_name::<T>(),)
                    })
                }
            }

            pub struct Usize1 {}
            impl Token for Usize1 {
                type Output = usize;
                fn parse(s: &str) -> Self::Output {
                    usize::parse(s)
                        .checked_sub(1)
                        .expect("Parse error! (Zero substruction error of Usize1)")
                }
            }
        }

        mod multi_token {
            use super::{Token, Tokenizer};
            use std::{io::BufRead, iter, marker};

            pub trait Parser: Sized {
                type Output;
                fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output;
                fn vec(self, len: usize) -> VecLen<Self> {
                    VecLen { len, elem: self }
                }
            }
            pub struct Leaf<T>(pub(super) marker::PhantomData<T>);
            impl<T: Token> Parser for Leaf<T> {
                type Output = T::Output;
                fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> T::Output {
                    server.parse::<T>()
                }
            }

            pub struct VecLen<T> {
                pub len: usize,
                pub elem: T,
            }
            impl<T: Parser> Parser for VecLen<T> {
                type Output = Vec<T::Output>;
                fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output {
                    iter::repeat_with(|| self.elem.parse(server))
                        .take(self.len)
                        .collect()
                }
            }

            pub trait RawTuple {
                type LeafTuple: Parser;
                fn leaf_tuple() -> Self::LeafTuple;
            }
            pub trait ParserTuple {
                type Tuple: Parser;
                fn tuple(self) -> Self::Tuple;
            }
            pub struct Tuple<T>(pub T);
            macro_rules! impl_tuple {
                ($($t:ident: $T:ident),*) => {
                    impl<$($T),*> Parser for Tuple<($($T,)*)>
                        where
                            $($T: Parser,)*
                            {
                                type Output = ($($T::Output,)*);
#[allow(unused_variables)]
                                fn parse<S: BufRead >(&self, server: &mut Tokenizer<S>) -> Self::Output {
                                    match self {
                                        Tuple(($($t,)*)) => {
                                            ($($t.parse(server),)*)
                                        }
                                    }
                                }
                            }
                    impl<$($T: Token),*> RawTuple for ($($T,)*) {
                        type LeafTuple = Tuple<($(Leaf<$T>,)*)>;
                        fn leaf_tuple() -> Self::LeafTuple {
                            Tuple(($($T::leaf(),)*))
                        }
                    }
                    impl<$($T: Parser),*> ParserTuple for ($($T,)*) {
                        type Tuple = Tuple<($($T,)*)>;
                        fn tuple(self) -> Self::Tuple {
                            Tuple(self)
                        }
                    }
                };
            }
            impl_tuple!();
            impl_tuple!(t1: T1);
            impl_tuple!(t1: T1, t2: T2);
            impl_tuple!(t1: T1, t2: T2, t3: T3);
            impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4);
            impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5);
            impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6);
            impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7);
            impl_tuple!(
                t1: T1,
                t2: T2,
                t3: T3,
                t4: T4,
                t5: T5,
                t6: T6,
                t7: T7,
                t8: T8
            );
        }

        trait Scanner: BufRead + Sized {
            fn tokenizer(self) -> Tokenizer<Self> {
                Tokenizer::new(self)
            }
        }
        impl<R: BufRead> Scanner for R {}
    }

    pub use i::{with_stdin, with_str};

    pub mod prelude {
        pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1};
    }
}
// }}}


Measured memory_bytes: 9532