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 ) => { # [ doc = " Converts 1-origin integer into 0-origin when read from stdin." ] # [ doc = "" ] # [ doc = " # Example" ] # [ doc = "" ] # [ doc = " ```no_run" ] # [ doc = " # #[macro_use] extern crate atcoder_snippets;" ] # [ doc = " # use atcoder_snippets::read::*;" ] # [ doc = " // Stdin: \"1\"" ] # [ doc = " read!(a = usize_);" ] # [ doc = " assert_eq!(a, 0);" ] # [ doc = " ```" ] # [ 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 t4 , T3 t3 , T2 t2 , T1 t1 ) ; } ; ( $ 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 t4 , T3 t3 , T2 t2 , T1 t1 ) ; } }
readable_collection ! ( U => Vec < U >, Vec < U :: Output > ) ;
readable_collection ! ( U : Eq , std :: hash :: Hash => std :: collections :: HashSet < U >, std :: collections :: HashSet < 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()
    }
}

pub struct SegmentTree<T: Clone, F: Fn(&T, &T) -> T> {
    heap: Vec<T>,
    identity: T,
    aggregate: F,
}
mod segment_tree_internal {
    pub fn parent_of(heap_index: usize) -> usize {
        (heap_index - 1) / 2
    }
    pub fn left_of(heap_index: usize) -> usize {
        heap_index * 2 + 1
    }
    pub fn right_of(heap_index: usize) -> usize {
        left_of(heap_index) + 1
    }
    pub fn is_root_or_right(heap_index: usize) -> bool {
        heap_index % 2 == 0
    }
}
impl<T: Clone, F: Fn(&T, &T) -> T> SegmentTree<T, F> {
    pub fn new(len: usize, identity: T, aggregate: F) -> SegmentTree<T, F> {
        SegmentTree {
            heap: vec![identity.clone(); (len * 2).saturating_sub(1)],
            identity: identity,
            aggregate: aggregate,
        }
    }
    pub fn from_vec(mut items: Vec<T>, identity: T, aggregate: F) -> SegmentTree<T, F> {
        use self::segment_tree_internal::*;
        let node_count = items.len().saturating_sub(1);
        let mut heap = Vec::with_capacity(node_count + items.len());
        unsafe {
            heap.set_len(node_count);
        }
        heap.append(&mut items);
        for i in (0..node_count).rev() {
            heap[i] = aggregate(&heap[left_of(i)], &heap[right_of(i)]);
        }
        SegmentTree {
            heap: heap,
            identity: identity,
            aggregate: aggregate,
        }
    }
    fn node_count(&self) -> usize {
        self.heap.len() / 2
    }
    pub fn len(&self) -> usize {
        self.heap.len() - self.node_count()
    }
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    pub fn items(&self) -> &[T] {
        &self.heap[self.node_count()..self.node_count() + self.len()]
    }
    pub fn query(&self, range: std::ops::Range<usize>) -> Option<T> {
        if self.len() <= range.start {
            return None;
        }
        if self.len() < range.end {
            return None;
        }
        if range.start <= range.end {
            Some(self.aggregate_interval(
                self.node_count() + range.start,
                self.node_count() + range.end,
                self.identity.clone(),
                self.identity.clone(),
            ))
        } else {
            None
        }
    }
    fn aggregate_interval(
        &self,
        mut heap_start: usize,
        mut heap_end: usize,
        mut acc_left: T,
        mut acc_right: T,
    ) -> T {
        use self::segment_tree_internal::*;
        if heap_end == heap_start {
            (self.aggregate)(&acc_left, &acc_right)
        } else {
            if is_root_or_right(heap_start) {
                acc_left = (self.aggregate)(&acc_left, &self.heap[heap_start]);
                heap_start += 1;
            }
            if is_root_or_right(heap_end) {
                heap_end -= 1;
                acc_right = (self.aggregate)(&self.heap[heap_end], &acc_right);
            }
            self.aggregate_interval(
                parent_of(heap_start),
                parent_of(heap_end),
                acc_left,
                acc_right,
            )
        }
    }
    pub fn get_mut(&mut self, index: usize) -> Option<SegmentTreeItemRef<T, F>> {
        if index < self.len() {
            let heap_index = self.node_count() + index;
            Some(SegmentTreeItemRef {
                tree: self,
                heap_index: heap_index,
            })
        } else {
            None
        }
    }
    pub fn at(&mut self, index: usize) -> SegmentTreeItemRef<T, F> {
        self.get_mut(index).unwrap()
    }
    fn update_ancestors(&mut self, heap_index: usize) {
        use self::segment_tree_internal::*;
        if heap_index != 0 {
            let parent = parent_of(heap_index);
            let l = left_of(parent);
            let r = right_of(parent);
            self.heap[parent] = (self.aggregate)(&self.heap[l], &self.heap[r]);
            self.update_ancestors(parent);
        }
    }
}
pub struct SegmentTreeItemRef<'a, T: 'a + Clone, F: 'a + Fn(&T, &T) -> T> {
    tree: &'a mut SegmentTree<T, F>,
    heap_index: usize,
}
impl<'a, T, F> std::ops::Deref for SegmentTreeItemRef<'a, T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    type Target = T;
    fn deref(&self) -> &T {
        &self.tree.heap[self.heap_index]
    }
}
impl<'a, T, F> std::ops::DerefMut for SegmentTreeItemRef<'a, T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    fn deref_mut(&mut self) -> &mut T {
        &mut self.tree.heap[self.heap_index]
    }
}
impl<'a, T, F> Drop for SegmentTreeItemRef<'a, T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    fn drop(&mut self) {
        self.tree.update_ancestors(self.heap_index);
    }
}
pub trait IteratorExtForSegmentTree: Sized + Iterator
where
    Self::Item: Clone,
{
    fn segment_tree<F>(self, identity: Self::Item, aggregate: F) -> SegmentTree<Self::Item, F>
    where
        F: Fn(&Self::Item, &Self::Item) -> Self::Item,
    {
        SegmentTree::from_vec(self.collect(), identity, aggregate)
    }
}
impl<I: Iterator> IteratorExtForSegmentTree for I where <I as Iterator>::Item: Clone {}

pub type ModPBase = u64;
pub const MODULUS: ModPBase = 998244353;
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct ModP {
    base: ModPBase,
}
impl ModP {
    pub fn new(n: ModPBase) -> ModP {
        if !cfg!(test) {
            assert!(
                MODULUS != 7,
                "Set const MODULUS to the value provided by the problem."
            );
        }
        ModP { base: n % 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(MODULUS - 2)
    }
}
pub fn modp(x: u64) -> 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 % MODULUS
    }
}
impl PartialEq<ModP> for ModPBase {
    fn eq(&self, other: &ModP) -> bool {
        self % MODULUS == other.base() % MODULUS
    }
}
impl std::ops::Add for ModP {
    type Output = ModP;
    fn add(self, rhs: ModP) -> ModP {
        ModP {
            base: (self.base() + rhs.base() % MODULUS) % MODULUS,
        }
    }
}
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(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 {
        ModP {
            base: self.base() * (rhs.base() % MODULUS) % MODULUS,
        }
    }
}
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::<u64>()));

#[macro_export]
    #[cfg(local)]
    macro_rules! dbg {
    ( ) => {{
        use std::io::{self, Write};
        writeln!(io::stderr(), "{}: dbg", line!()).unwrap();
    }};
    ( $ e : expr ) => {{
        use std::io::{self, Write};
        let result = $e;
        writeln!(
            io::stderr(),
            "{}: {} = {:?}",
            line!(),
            stringify!($e),
            result
        )
            .unwrap();
        result
    }};
}
#[macro_export]
#[cfg(not(local))]
macro_rules! dbg {
    ( ) => {};
    ( $ e : expr ) => {
        $e
    };
}

use std::collections::HashMap;

fn pow(base: ModP, exp: usize) -> ModP {
    if exp == 0 { modp(1) } else {
        let half = pow(base, exp / 2);
        if exp % 2 == 0 {
            half * half
        } else {
            base * half * half
        }
    }
}

fn main() {
    read!(n = usize);
    let mut ps = readx::<(i32, i32)>();

    ps.sort_by_key(|p| p.0);
    let mut x_map = HashMap::new();
    for (i, x) in ps.iter().map(|&(x, _)| x).enumerate() {
        x_map.insert(x, i);
    }

    ps.sort_by_key(|p| p.1);
    let ps: Vec<(usize, usize)> = ps.into_iter().enumerate()
        .map(|(i, (x, _))| (x_map[&x], i))
        .collect();

    let mut tree_d = SegmentTree::new(n, 0usize, |&a, &b| a+b);
    let mut tree_u = SegmentTree::new(n, 0usize, |&a, &b| a+b);
    for i in 0..n {
        *tree_u.at(i) = 1;
    }
    let mut quadrants = Vec::new();
    for &(x, _) in &ps {
        *tree_u.at(x) = 0;

        let n1 = tree_u.query(x..n).unwrap();
        let n2 = tree_u.query(0..x).unwrap();
        let n3 = tree_d.query(0..x).unwrap();
        let n4 = tree_d.query(x..n).unwrap();
        quadrants.push([n1, n2, n3, n4]);

        *tree_d.at(x) = 1;
    }

    let included = pow(modp(2), n-1) * modp(n as u64);
    let excluded: ModP = (0..n).map(|i| {
        let ps: Vec<ModP> = quadrants[i].iter().map(|&n| pow(modp(2), n)).collect();
        (ps[0]-1) * (ps[2]-1) * ps[1] * ps[3] +
            (ps[1]-1) * (ps[3]-1) * ps[0] * ps[2] -
            (ps[0]-1) * (ps[1]-1) * (ps[2]-1) * (ps[3]-1)
    }).sum();
    println!("{}", included + excluded);
}


Measured memory_bytes: 31032