// SNIPPET read
pub trait Readable {
    type Output;
    fn words_count() -> usize;
    fn read_words(words: &[&str]) -> Result<Self::Output, String>;
}
#[macro_export]
macro_rules! readable {
    ( $t:ty, $words_count:expr, |$words:ident| $read_words:expr ) => {
        impl Readable for $t {
            type Output = $t;
            fn words_count() -> usize { $words_count }
            fn read_words($words: &[&str]) -> Result<$t, String> {
                Ok($read_words)
            }
        }
    };
}
readable!((), 1, |_ss| ());
readable!(String, 1, |ss| ss[0].to_string());
impl Readable for char {
    type Output = char;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<char, String> {
        let chars: Vec<char> = words[0].chars().collect();
        if chars.len() == 1 {
            Ok(chars[0])
        } else {
            Err(format!("cannot parse `{}` as a char", words[0]))
        }
    }
}
pub struct Chars();
impl Readable for Chars {
    type Output = Vec<char>;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Vec<char>, String> {
        Ok(words[0].chars().collect())
    }
}
macro_rules! impl_readable_for_ints {
    ( $( $t:ty )* ) => { $(
        impl Readable for $t {
            type Output = Self;
            fn words_count() -> usize { 1 }
            fn read_words(words: &[&str]) -> Result<$t, String> {
                use std::str::FromStr;
                <$t>::from_str(words[0]).map_err(|_| {
                    format!("cannot parse `{}` as {}", words[0], stringify!($t))
                })
            }
        }
    )* };
}
impl_readable_for_ints!(i8 u8 i16 u16 i32 u32 i64 u64 isize usize f32 f64);
macro_rules! define_one_origin_int_types {
    ( $new_t:ident $int_t:ty ) => {
        #[allow(non_camel_case_types)]
        pub struct $new_t;
        impl Readable for $new_t {
            type Output = $int_t;
            fn words_count() -> usize { 1 }
            fn read_words(words: &[&str]) -> Result<Self::Output, String> {
                <$int_t>::read_words(words).map(|n| n-1)
            }
        }
    };
    ( $new_t:ident $int_t:ty; $( $inner_new_t:ident $inner_int_t:ty );* ) => {
        define_one_origin_int_types!($new_t $int_t);
        define_one_origin_int_types!($($inner_new_t $inner_int_t);*);
    };
}
define_one_origin_int_types!(u8_ u8; u16_ u16; u32_ u32; u64_ u64; usize_ usize);
macro_rules! impl_readable_for_tuples {
    ( $t:ident $var:ident ) => ();
    ( $t:ident $var:ident; $( $inner_t:ident $inner_var:ident );* ) => {
        impl_readable_for_tuples!($($inner_t $inner_var);*);
        impl<$t: Readable, $($inner_t: Readable),*> Readable
            for ($t, $($inner_t),*)
        {
            type Output = ( <$t>::Output, $(<$inner_t>::Output),* );
            fn words_count() -> usize {
                let mut n = <$t>::words_count();
                $(
                    n += <$inner_t>::words_count();
                )*
                n
            }
            #[allow(unused_assignments)]
            fn read_words(words: &[&str]) ->
                Result<Self::Output, String>
            {
                let mut start = 0;
                let $var = <$t>::read_words(
                    &words[start .. start+<$t>::words_count()]
                )?;
                start += <$t>::words_count();
                $(
                    let $inner_var =
                        <$inner_t>::read_words(
                            &words[start .. start+<$inner_t>::words_count()]
                        )?;
                    start += <$inner_t>::words_count();
                )*
                Ok(( $var, $($inner_var),* ))
            }
        }
    };
}
impl_readable_for_tuples!(T8 x8; T7 x7; T6 x6; T5 x5; T4 x4; T3 x3; T2 x2; T1 x1);
pub trait ReadableFromLine {
    type Output;
    fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
    #[allow(deprecated)]
    line.trim_right_matches('\n').split_whitespace().collect()
}
impl<T: Readable> ReadableFromLine for T {
    type Output = T::Output;
    fn read_line(line: &str) -> Result<T::Output, String> {
        let words = split_into_words(line);
        if words.len() != T::words_count() {
            return Err(format!("line `{}` has {} words, expected {}",
                               line, words.len(), T::words_count()));
        }
        T::read_words(&words)
    }
}
macro_rules! impl_readable_from_line_for_tuples_with_from_iterator {
    ( $u:ident : $( + $bound:path )* => $seq_in:ty, $seq_out:ty; $t:ident $var:ident ) => {
        impl<$u: Readable> ReadableFromLine for $seq_in
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = $seq_out;
            fn read_line(line: &str) -> Result<$seq_out, String> {
                let n = $u::words_count();
                let words = split_into_words(line);
                if words.len() % n != 0 {
                    return Err(format!("line `{}` has {} words, expected multiple of {}",
                                       line, words.len(), n));
                }
                let mut result = Vec::new();
                for chunk in words.chunks(n) {
                    match $u::read_words(chunk) {
                        Ok(v) => result.push(v),
                        Err(msg) => {
                            let flagment_msg = if n == 1 {
                                format!("word {}", result.len())
                            } else {
                                let l = result.len();
                                format!("words {}-{}", n*l + 1, (n+1) * l)
                            };
                            return Err(format!(
                                "{} of line `{}`: {}", flagment_msg, line, msg
                            ));
                        }
                    }
                }
                Ok(result.into_iter().collect())
            }
        }
        impl<T: Readable, $u: Readable> ReadableFromLine for (T, $seq_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T::Output, $seq_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let n = T::words_count();
                #[allow(deprecated)]
                let trimmed = line.trim_right_matches('\n');
                let words_and_rest: Vec<&str> = trimmed.splitn(n + 1, ' ').collect();
                if words_and_rest.len() < n {
                    return Err(format!("line `{}` has {} words, expected at least {}",
                                       line, words_and_rest.len(), n));
                }
                let words = &words_and_rest[..n];
                let empty_str = "";
                let rest = words_and_rest.get(n).unwrap_or(&empty_str);
                Ok((T::read_words(words)?, <$seq_in>::read_line(rest)?))
            }
        }
    };
    ( $u:ident : $( + $bound:path )* => $seq_in:ty, $seq_out:ty;
      $t:ident $var:ident, $( $inner_t:ident $inner_var:ident ),+ ) => {
        impl_readable_from_line_for_tuples_with_from_iterator!(
            $u: $(+ $bound)* => $seq_in, $seq_out; $($inner_t $inner_var),+
        );
        impl<$t: Readable, $($inner_t: Readable),+ , $u: Readable> ReadableFromLine
            for ($t, $($inner_t),+ , $seq_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = ($t::Output, $($inner_t::Output),+ , $seq_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let mut n = $t::words_count();
                $(
                    n += $inner_t::words_count();
                )+
                #[allow(deprecated)]
                let trimmed = line.trim_right_matches('\n');
                let words_and_rest: Vec<&str> = trimmed.splitn(n + 1, ' ')
                    .collect();
                if words_and_rest.len() < n {
                    return Err(
                        format!("line `{}` has {} words, expected at least {}",
                                line, words_and_rest.len(), n)
                    );
                }
                let words = &words_and_rest[..n];
                let empty_str = "";
                let rest = words_and_rest.get(n).unwrap_or(&empty_str);
                let ($var, $($inner_var),*) =
                    <($t, $($inner_t),+)>::read_words(words)?;
                Ok(($var, $($inner_var),* , <$seq_in>::read_line(rest)?))
            }
        }
    };
}
#[macro_export]
macro_rules! readable_collection {
    ($u:ident => $collection_in:ty, $collection_out:ty) => {
        impl_readable_from_line_for_tuples_with_from_iterator!(
            $u: => $collection_in, $collection_out;
            T8 x8, T7 x7, T6 x6, T5 x5, T4 x4, T3 x3, T2 x2, T1 x1
        );
    };
    ($u:ident : $( $bound:path ),* => $collection_in:ty, $collection_out:ty) => {
        impl_readable_from_line_for_tuples_with_from_iterator!(
            $u: $(+ $bound)* => $collection_in, $collection_out;
            T8 x8, T7 x7, T6 x6, T5 x5, T4 x4, T3 x3, T2 x2, T1 x1
        );
    }
}
readable_collection!(U => Vec<U>, Vec<U::Output>);
readable_collection!(
    U => std::collections::VecDeque<U>, std::collections::VecDeque<U::Output>
);
readable_collection!(
    U: Eq, std::hash::Hash => std::collections::HashSet<U>, std::collections::HashSet<U::Output>
);
readable_collection!(
    U: Ord => std::collections::BTreeSet<U>, std::collections::BTreeSet<U::Output>
);
readable_collection!(
    U: Ord => std::collections::BinaryHeap<U>, std::collections::BinaryHeap<U::Output>
);
pub fn read<T: ReadableFromLine>() -> T::Output {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    T::read_line(&line).unwrap()
}
#[macro_export]
macro_rules! read {
    () => {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
    };
    ( $pat:pat = $t:ty ) => {
        let $pat = read::<$t>();
    };
    ( $( $pat:pat = $t:ty ),+ ) => {
        read!(($($pat),*) = ($($t),*));
    };
}
#[macro_export]
macro_rules! readls {
    ( $( $pat:pat = $t:ty ),+ ) => {
        $(
            read!($pat = $t);
        )*
    };
}
pub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result = stdin.lock().lines().map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    result
}
#[macro_export]
macro_rules! readx_loop {
    ( |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            for line in stdin.lock().lines() {
                let line = line.expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( |$($pat:pat = $t:ty),*| $body:expr ) => {
        readx_loop!(|($($pat),*) = ($($t),*)| $body);
    };
}
pub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result: Vec<T::Output> = stdin.lock().lines().take(n).map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    if result.len() < n {
        panic!("expected reading {} lines, but only {} lines are read",
               n, result.len());
    }
    result
}
#[macro_export]
macro_rules! readn_loop {
    ( $n:expr, |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            let mut lock = stdin.lock();
            for _ in 0..$n {
                let mut line = String::new();
                lock.read_line(&mut line).expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( $n:expr, |$($pat:pat = $t:ty),*| $body:expr ) => {
        readn_loop!($n, |($($pat),*) = ($($t),*)| $body);
    };
}
pub trait Words {
    fn read<T: Readable>(&self) -> T::Output;
}
impl<'a> Words for [&'a str] {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(self).unwrap()
    }
}
impl<'a> Words for &'a str {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(&[self]).unwrap()
    }
}
// SNIPPET iter
#[derive(Clone)]
pub struct StepBy<I> {
    iter: I,
    step: usize,
    first_take: bool
}
impl<I: Iterator> Iterator for StepBy<I> {
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> {
        if self.first_take {
            self.first_take = false;
            self.iter.next()
        } else {
            self.iter.nth(self.step)
        }
    }
}
pub struct Chunks<I: Iterator> {
    iter: I,
    size: usize
}
impl<I: Iterator> Iterator for Chunks<I> {
    type Item = Vec<I::Item>;
    fn next(&mut self) -> Option<Self::Item> {
        let first = self.iter.next();
        if first.is_none() {
            return None;
        }
        let mut chunk = Vec::with_capacity(self.size);
        chunk.push(first.unwrap());
        for _ in 0..self.size-1 {
            match self.iter.next() {
                Some(x) => chunk.push(x),
                None => break
            }
        }
        Some(chunk)
    }
}
#[derive(Clone)]
pub struct LScan<I: Iterator, S: Clone, F: FnMut(&S, I::Item) -> S> {
    iter: I,
    state: Option<S>,
    f: F,
}
impl<I: Iterator, S: Clone, F> Iterator for LScan<I, S, F>
where
    F: FnMut(&S, I::Item) -> S,
{
    type Item = S;
    fn next(&mut self) -> Option<S> {
        if self.state.is_none() {
            return None;
        }
        let state_inner = self.state.take().unwrap();
        if let Some(item) = self.iter.next() {
            self.state = Some((self.f)(&state_inner, item));
        }
        Some(state_inner)
    }
}
pub struct Flatten<I: Iterator>
where
    I::Item: IntoIterator
{
    outer_iter: I,
    inner_iter: Option<<<I as Iterator>::Item as IntoIterator>::IntoIter>
}
impl<I, J> Iterator for Flatten<I>
where
    I: Iterator<Item = J>,
    J: IntoIterator
{
    type Item = <<J as IntoIterator>::IntoIter as Iterator>::Item;
    fn next(&mut self) -> Option<J::Item> {
        loop {
            if let Some(inner_iter) = self.inner_iter.as_mut() {
                if let item@Some(_) = inner_iter.next() {
                    return item
                }
            }
            match self.outer_iter.next() {
                None => return None,
                Some(inner) => self.inner_iter = Some(inner.into_iter())
            }
        }
    }
}
/*
impl<I, J> DoubleEndedIterator for Flatten<I>
where
    I: DoubleEndedIterator,
    J: DoubleEndedIterator,
    I::Item: J {}
*/
pub struct GroupBy<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> {
    cur: Option<(I::Item, K)>,
    iter: I,
    key_fn: F
}
impl<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> Iterator for GroupBy<K, I, F> {
    type Item = (K, Vec<I::Item>);
    fn next(&mut self) -> Option<(K, Vec<I::Item>)> {
        let cur = self.cur.take();
        cur.map(|(item, key)| {
            let mut group = vec![item];
            loop {
                let next = self.iter.next();
                match next {
                    Some(next_item) => {
                        let next_key = (self.key_fn)(&next_item);
                        if key == next_key {
                            group.push(next_item);
                        } else {
                            self.cur = Some((next_item, next_key));
                            break;
                        }
                    }
                    None => {
                        self.cur = None;
                        break;
                    }
                }
            }
            (key, group)
        })
    }
}
pub struct RunLength<I: Iterator> {
    cur: Option<I::Item>,
    iter: I
}
impl<I: Iterator> Iterator for RunLength<I> where I::Item: Eq {
    type Item = (I::Item, usize);
    fn next(&mut self) -> Option<(I::Item, usize)> {
        let cur = self.cur.take();
        cur.map(|value| {
            let mut length = 1;
            loop {
                let next = self.iter.next();
                match next {
                    Some(next_value) => {
                        if value == next_value {
                            length += 1;
                        } else {
                            self.cur = Some(next_value);
                            break;
                        }
                    }
                    None => {
                        self.cur = None;
                        break;
                    }
                }
            }
            (value, length)
        })
    }
}
pub trait IteratorExt: Iterator {
    fn step_by_(self, step: usize) -> StepBy<Self> where Self: Sized {
        assert_ne!(step, 0);
        StepBy {
            iter: self,
            step: step - 1,
            first_take: true
        }
    }
    fn for_each<F: FnMut(Self::Item)>(self, mut f: F) where Self: Sized {
        for item in self {
            f(item);
        }
    }
    fn chunks(self, size: usize) -> Chunks<Self> where Self: Sized {
        assert!(size > 0);
        Chunks {
            iter: self,
            size: size
        }
    }
    fn lscan<S: Clone, F>(self, state: S, f: F) -> LScan<Self, S, F>
    where
        Self: Sized,
        F: FnMut(&S, Self::Item) -> S,
    {
        LScan {
            iter: self,
            state: Some(state),
            f: f,
        }
    }
    fn get_unique(mut self) -> Option<Self::Item> where Self: Sized, Self::Item: Eq {
        let first_opt = self.next();
        first_opt.and_then(|first| {
            if self.all(|item| item == first) { Some(first) } else { None }
        })
    }
    fn flatten(mut self) -> Flatten<Self> where Self: Sized, Self::Item: IntoIterator {
        let inner_opt = self.next();
        Flatten {
            outer_iter: self,
            inner_iter: inner_opt.map(|inner| inner.into_iter())
        }
    }
    fn group_by<K: Eq, F: FnMut(&Self::Item) -> K>(mut self, mut f: F) -> GroupBy<K, Self, F> where Self: Sized {
        let next = self.next();
        GroupBy {
            cur: next.map(|item| {
                let key = f(&item);
                (item, key)
            }),
            iter: self,
            key_fn: f
        }
    }
    fn run_length(mut self) -> RunLength<Self> where Self: Sized, Self::Item: Eq {
        RunLength {
            cur: self.next(),
            iter: self
        }
    }
    fn join<T: std::fmt::Display>(mut self, sep: T) -> String
    where
        Self: Sized, Self::Item: std::fmt::Display
    {
        let mut result = String::new();
        if let Some(first) = self.next() {
            result.push_str(&format!("{}", first));
        }
        for s in self {
            result.push_str(&format!("{}{}", sep, s));
        }
        result
    }
    fn cat(self) -> String where Self: Sized, Self::Item: std::fmt::Display { self.join("") }
}
impl<I: Iterator> IteratorExt for I {}
pub struct Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    state: Option<T>,
    f: F
}
impl<T, F> Iterator for Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.state.is_none() {
            return None;
        }
        let state_inner = self.state.take().unwrap();
        self.state = (self.f)(&state_inner);
        Some(state_inner)
    }
}
pub fn unfold<T, F>(init: T, f: F) -> Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    Unfold { state: Some(init), f: f }
}
pub struct Iterate<T, F> where F: FnMut(&T) -> T {
    state: T,
    f: F
}
impl<T, F> Iterator for Iterate<T, F> where F: FnMut(&T) -> T {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        use std::mem::swap;
        let mut state = (self.f)(&self.state);
        swap(&mut state, &mut self.state);
        Some(state)
    }
}
pub fn iterate<T, F>(init: T, f: F) -> Iterate<T, F>
where
    F: FnMut(&T) -> T,
{
    Iterate { state: init, f: f }
}
// SNIPPET modp
pub type ModPBase = u64;
pub type ModPModulus = u32;
static mut MODULUS: ModPBase = 0;
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct ModP {
    base: ModPBase
}
impl ModP {
    pub unsafe fn set_mod(modulus: ModPModulus) -> Result<(), String> {
        if modulus <= 1 {
            return Err(format!("{} is not a prime number.", modulus));
        }
        if modulus >= 4 {
            if modulus % 2 == 0 || modulus % 3 == 0 {
                return Err(format!("{} is not a prime number.", modulus));
            }
            let mut divisor = 5;
            loop {
                if divisor * divisor > modulus {
                    break;
                }
                if modulus % divisor == 0 {
                    return Err(format!("{} is not a prime number.", modulus));
                }
                divisor += 2;
                if divisor * divisor > modulus {
                    break;
                }
                if modulus % divisor == 0 {
                    return Err(format!("{} is not a prime number.", modulus));
                }
                divisor += 4;
            }
        }
        MODULUS = modulus as ModPBase;
        Ok(())
    }
    pub fn new(n: ModPBase) -> ModP {
        if !cfg!(test) {
            assert!(unsafe { MODULUS } != 0,
                    "Call ModP::set_mod before using ModP.");
        }
        ModP { base: n % unsafe { MODULUS } }
    }
    pub unsafe fn new_unchecked(n: ModPBase) -> ModP {
        ModP { base: n }
    }
    pub fn base(&self) -> ModPBase {
        self.base
    }
    pub fn pow(self, exp: ModPBase) -> ModP {
        if exp == 0 { ModP::new(1) } else {
            let sub = self.pow(exp / 2);
            if exp % 2 == 0 {
                sub * sub
            } else {
                self * sub * sub
            }
        }
    }
    pub fn inv(self) -> ModP {
        assert!(self.base() != 0);
        self.pow(unsafe { MODULUS } - 2)
    }
}
pub fn modp(x: ModPBase) -> ModP {
    ModP::new(x)
}
impl std::fmt::Display for ModP {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.base())
    }
}
impl std::fmt::Debug for ModP {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{} mod P", self.base())
    }
}
impl PartialEq<ModPBase> for ModP {
    fn eq(&self, other: &ModPBase) -> bool {
        self.base() == other % unsafe { MODULUS }
    }
}
impl PartialEq<ModP> for ModPBase {
    fn eq(&self, other: &ModP) -> bool {
        self % unsafe { MODULUS } == other.base() % unsafe { MODULUS }
    }
}
impl std::ops::Add for ModP {
    type Output = ModP;
    fn add(self, rhs: ModP) -> ModP {
        let m = unsafe { MODULUS };
        ModP { base: (self.base() + rhs.base() % m) % m }
    }
}
impl std::ops::Add<ModPBase> for ModP {
    type Output = ModP;
    fn add(self, rhs: ModPBase) -> ModP {
        self + ModP::new(rhs)
    }
}
impl std::ops::Add<ModP> for ModPBase {
    type Output = ModP;
    fn add(self, rhs: ModP) -> ModP {
        ModP::new(self) + rhs.base()
    }
}
impl std::ops::AddAssign for ModP {
    fn add_assign(&mut self, rhs: ModP) {
        *self = *self + rhs
    }
}
impl std::ops::AddAssign<ModPBase> for ModP {
    fn add_assign(&mut self, rhs: ModPBase) {
        *self = *self + ModP::new(rhs)
    }
}
impl std::ops::Neg for ModP {
    type Output = ModP;
    fn neg(self) -> ModP {
        ModP::new(unsafe { MODULUS } - self.base())
    }
}
impl std::ops::Sub for ModP {
    type Output = ModP;
    fn sub(self, rhs: ModP) -> ModP {
        self + (-rhs)
    }
}
impl std::ops::Sub<ModPBase> for ModP {
    type Output = ModP;
    fn sub(self, rhs: ModPBase) -> ModP {
        self - ModP::new(rhs)
    }
}
impl std::ops::Sub<ModP> for ModPBase {
    type Output = ModP;
    fn sub(self, rhs: ModP) -> ModP {
        ModP::new(self) - rhs
    }
}
impl std::ops::SubAssign for ModP {
    fn sub_assign(&mut self, rhs: ModP) {
        *self = *self - rhs;
    }
}
impl std::ops::SubAssign<ModPBase> for ModP {
    fn sub_assign(&mut self, rhs: ModPBase) {
        *self = *self - ModP::new(rhs)
    }
}
impl std::ops::Mul for ModP {
    type Output = ModP;
    fn mul(self, rhs: ModP) -> ModP {
        let m = unsafe { MODULUS };
        ModP { base: self.base() * (rhs.base() % m) % m }
    }
}
impl std::ops::Mul<ModPBase> for ModP {
    type Output = ModP;
    fn mul(self, rhs: ModPBase) -> ModP {
        self * ModP::new(rhs)
    }
}
impl std::ops::Mul<ModP> for ModPBase {
    type Output = ModP;
    fn mul(self, rhs: ModP) -> ModP {
        ModP::new(self) * rhs.base()
    }
}
impl std::ops::MulAssign for ModP {
    fn mul_assign(&mut self, rhs: ModP) {
        *self = *self * rhs
    }
}
impl std::ops::MulAssign<ModPBase> for ModP {
    fn mul_assign(&mut self, rhs: ModPBase) {
        *self = *self * ModP::new(rhs)
    }
}
impl std::ops::Div for ModP {
    type Output = ModP;
    fn div(self, rhs: ModP) -> ModP {
        self * rhs.inv()
    }
}
impl std::ops::Div<ModPBase> for ModP {
    type Output = ModP;
    fn div(self, rhs: ModPBase) -> ModP {
        self * ModP::new(rhs).inv()
    }
}
impl std::ops::Div<ModP> for ModPBase {
    type Output = ModP;
    fn div(self, rhs: ModP) -> ModP {
        ModP::new(self) * rhs.inv()
    }
}
impl std::ops::DivAssign for ModP {
    fn div_assign(&mut self, rhs: ModP) {
        *self = *self / rhs;
    }
}
impl std::ops::DivAssign<ModPBase> for ModP {
    fn div_assign(&mut self, rhs: ModPBase) {
        *self = *self / ModP::new(rhs)
    }
}
impl std::iter::Sum for ModP {
    fn sum<I: Iterator<Item=ModP>>(iter: I) -> ModP {
        let mut ans = 0;
        for n in iter {
            ans += n.base();
        }
        ModP::new(ans)
    }
}
impl<'a> std::iter::Sum<&'a ModP> for ModP {
    fn sum<I: Iterator<Item=&'a ModP>>(iter: I) -> ModP {
        let mut ans = 0;
        for n in iter {
            ans += n.base();
        }
        ModP::new(ans)
    }
}
impl std::iter::Product for ModP {
    fn product<I: Iterator<Item=ModP>>(iter: I) -> ModP {
        let mut ans = unsafe { ModP::new_unchecked(1) };
        for n in iter {
            ans *= n;
        }
        ans
    }
}
impl<'a> std::iter::Product<&'a ModP> for ModP {
    fn product<I: Iterator<Item=&'a ModP>>(iter: I) -> ModP {
        let mut ans = unsafe { ModP::new_unchecked(1) };
        for &n in iter {
            ans *= n;
        }
        ans
    }
}
readable!(ModP, 1, |ws| ModP::new(ws[0].read::<ModPBase>()));
// END SNIPPETS

fn choose(n: u64, m: u64, fs: &[ModP]) -> ModP {
    fs[n as usize] / (fs[(n-m) as usize] * fs[m as usize])
}

fn calc(a: u64, b: u64, n: u64, fs: &[ModP]) -> ModP {
    choose(n, a, fs) * choose(n, b, fs)
}

fn main() {
    unsafe { ModP::set_mod(998244353).unwrap(); }
    read!(n = u64, a = u64, b = u64, k = u64);
    let fs: Vec<ModP> = (1..n+1).lscan(modp(1), |&acc, i| acc * i).collect();
    let ans: ModP = (0..n+1).map(|i_a| {
        k.checked_sub(i_a * a).map_or(modp(0), |rest| {
            if rest % b != 0 {
                return modp(0);
            }
            let i_b = rest / b;
            if i_b > n { modp(0) } else { calc(i_a, i_b, n, &fs) }
        })
    }).sum();
    println!("{}", ans);
}


Measured memory_bytes: 9464