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 struct Modulo1000000009 {}
    impl Modulus for Modulo1000000009 {
        #[inline]
        fn get_modulus() -> u32 {
            const MODULUS: u32 = 1_000_000_009;
            MODULUS
        }
    }
    pub struct Modulo998244353 {}
    impl Modulus for Modulo998244353 {
        #[inline]
        fn get_modulus() -> u32 {
            const MODULUS: u32 = 998_244_353;
            MODULUS
        }
    }
    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 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 * 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);
}
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);
}
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()
}
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 :ty ;$len :expr ] ) =>{scanner .scan_vec ::<$t >($len ) } ;([$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |scan !($t ) ) .collect ::<Vec <_ >>() } ;([$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 m = scan!();
    let a = scan!([M; n]);
    let b = scan!([M; m]);
    let c = NTT::convolve(a, b);
    echo!(c, " ");
}
type M = MInt<modulus::Modulo998244353>;
type NTT = NumberTheoreticTransform<modulus::Modulo998244353>;

Measured memory_bytes: 29280