#![allow(unused_imports)]

// language: Rust(1.42.0)
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"
// My Library Repositry is at "https://github.com/Loptall/sfcpl"

use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_complex::Complex;
use num_integer::{binomial, gcd, lcm, multinomial, Integer};
use num_rational::Rational;
use num_traits::{
    clamp, one, pow, zero, Num, NumAssignOps, NumOps, One, Pow, Signed, Unsigned, Zero,
};
use permutohedron::Heap;
use proconio::{
    derive_readable, fastout, input, is_stdin_empty,
    marker::{Bytes, Chars, Isize1, Usize1},
};
use rand::random;
use std::cmp::{
    max, min, Ordering,
    Ordering::{Equal, Greater, Less},
    Reverse,
};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::convert::TryInto;
use std::fmt;
use std::mem::swap;
use std::num::{NonZeroU32, ParseIntError};
use std::ops::{
    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
    Index, IndexMut, Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
    SubAssign,
};
use std::process::exit;
use std::{f32, f64, i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

pub use visualize::*;
pub mod visualize {
    use itertools::*;
    pub trait Visualize {
        fn visualize(&self, split: &str);
        fn continuous(&self) {
            self.visualize("");
        }
        fn spaces(&self) {
            self.visualize(" ");
        }
        fn lines(&self) {
            self.visualize("\n");
        }
    }
    macro_rules ! impl_vis_for_sized {($ ($ t : ty ) ,+ ) => {$ (impl Visualize for $ t {fn visualize (& self , _split : & str ) {print ! ("{}" , self ) ; } } ) + } ; }
    impl_vis_for_sized! {usize , u8 , u16 , u32 , u64 , u128 , isize , i8 , i16 , i32 , i64 , i128 , String , & str , char }
    impl<T: std::fmt::Display> Visualize for [T] {
        fn visualize(&self, split: &str) {
            print!("{}", self.iter().join(split));
        }
    }
    #[macro_export]
    macro_rules ! vis {() => {println ! () ; } ; ($ last : expr ; ) => {$ last . lines () ; vis ! () } ; ($ last : expr => ) => {$ last . continuous () ; vis ! () ; } ; ($ last : expr $ (, ) ? ) => {$ last . spaces () ; vis ! () ; } ; ($ first : expr ; $ ($ rest : tt ) * ) => {$ first . lines () ; println ! () ; vis ! ($ ($ rest ) * ) ; } ; ($ first : expr => $ ($ rest : tt ) * ) => {$ first . continuous () ; vis ! ($ ($ rest ) * ) ; } ; ($ first : expr , $ ($ rest : tt ) * ) => {$ first . spaces () ; print ! (" " ) ; vis ! ($ ($ rest ) * ) ; } ; }
}

pub use consts::*;
pub mod consts {
    pub const MOD10E9_7: usize = 1000000007; // 10 ^ 9 + 7
    pub const MOD99_: usize = 998244353;
    pub const MAX: usize = std::usize::MAX; // = 2 ^ 64 - 1 = 18446744073709551615 ≈ 1.8 * 10 ^ 19
    pub const INF: usize = 2000000000000000000; // MAX / 9 < 2 * 10e18 < MAX / 10
    pub const FNI: i64 = -2000000000000000000; // == -(INF as i64)
    pub const PI: f64 = std::f64::consts::PI; // 3.141592653589793 -- 10 ^ -15
    pub const ASCII_A_LARGE: u8 = 65;
    pub const ASCII_A_SMALL: u8 = 97;
    pub const ASCII_0: u8 = 48;
    pub const ADJ4: &[(isize, isize); 4] = &[(1, 0), (0, 1), (-1, 0), (0, -1)];
    pub const ADJ8: &[(isize, isize); 8] = &[
        (1, 0),
        (1, 1),
        (0, 1),
        (-1, 1),
        (-1, 0),
        (-1, -1),
        (0, -1),
        (1, -1),
    ];
}

// snippet here
pub use combinatorics::*;
pub mod combinatorics {
    use num_integer::Integer;
    use num_traits::{
        identities::{One, Zero},
        NumAssignOps, NumOps,
    };
    use num_traits::{Num, Pow};
    use std::cmp::Ordering;
    use std::convert::TryInto;
    use std::num::NonZeroU32;
    use std::num::ParseIntError;
    use std::ops::{
        Add, AddAssign, Div, DivAssign, Mul, MulAssign, Rem, RemAssign, Sub, SubAssign,
    };
    /// n % m
    /// ただし答えが負になる場合は余分にmを足すことで一意な値を保証
    /// # Panic
    /// 異なるmod間での演算をattemptした時
    fn compensated_rem(n: i64, m: usize) -> i64 {
        match n % m as i64 {
            r if r >= 0 => r,
            r => r + m as i64,
        }
    }
    #[derive(Debug, Copy, Clone, Eq, PartialEq)]
    pub enum Modulo {
        Static(NonZeroU32),
        Dynamic,
    }
    impl Modulo {
        pub fn get(&self) -> Option<u32> {
            match self {
                Modulo::Static(nz) => Some(nz.get()),
                Modulo::Dynamic => None,
            }
        }
    }
    /// `ModInt -> PrimiteveInt` への暗黙のキャストは行わない!
    /// (get関数を提供するのでそれ使ってどうぞ)
    /// `PrimitiveInt -> ModInt` は許可する
    #[derive(Debug, Clone, Copy)]
    pub struct ModInt {
        num: i64,
        _modulo: Modulo,
    }
    impl Into<usize> for ModInt {
        fn into(self) -> usize {
            self.get() as usize
        }
    }
    pub trait IntoModInt: Copy {
        fn to_mint<M: TryInto<u32> + Copy>(self, modulo: M) -> ModInt;
    }
    macro_rules ! impl_into_mint {($ ($ t : ty ) ,* ) => {$ (impl IntoModInt for $ t {fn to_mint < M : TryInto < u32 > + Copy > (self , modulo : M ) -> ModInt {ModInt :: new (self , modulo ) } } ) * } ; }
    impl_into_mint!(usize, u8, u16, u32, u64, isize, i8, i16, i32, i64);
    impl PartialEq for ModInt {
        fn eq(&self, other: &Self) -> bool {
            if !check_mod_eq(self, other).1 {
                panic!("cannot compare these values because they have different modulo number",)
            }
            self.get() == other.num
        }
    }
    impl PartialOrd for ModInt {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            if !check_mod_eq(self, other).1 {
                None
            } else {
                Some(self.get().cmp(&other.num))
            }
        }
    }
    fn check_mod_eq(a: &ModInt, b: &ModInt) -> (NonZeroU32, bool) {
        match (a._modulo, b._modulo) {
            (Modulo::Static(a), Modulo::Static(b)) => {
                if a == b {
                    (a, true)
                } else {
                    (unsafe { NonZeroU32::new_unchecked(1) }, false)
                }
            }
            (Modulo::Static(m), Modulo::Dynamic) | (Modulo::Dynamic, Modulo::Static(m)) => {
                (m, true)
            }
            (Modulo::Dynamic, Modulo::Dynamic) => (unsafe { NonZeroU32::new_unchecked(1) }, false),
        }
    }
    impl ModInt {
        /// always `_modulo > num >= 0 && _modulo >= 1`
        pub fn new<N: TryInto<i64>, M: TryInto<u32> + Copy>(n: N, m: M) -> Self {
            let m =
                NonZeroU32::new(m.try_into().ok().expect("modulo number may be wrong")).unwrap();
            let r = n
                .try_into()
                .ok()
                .expect("modulo number maybe over i64 range");
            let num = compensated_rem(r, m.get() as usize);
            Self {
                num,
                _modulo: Modulo::Static(m),
            }
        }
        /// get inner value
        pub fn get(&self) -> i64 {
            self.num
        }
        /// mod of modint
        /// # Panic
        /// if variant is Modulo::Dynamic
        pub fn get_mod(&self) -> usize {
            self._modulo.get().unwrap() as usize
        }
        /// return the power of self with mod, using binary powering method
        /// cannot use of Dynamic type mod Self
        fn pow_mod(&self, mut exp: usize) -> Self {
            let mut res = 1;
            let mut base = self.get() as usize;
            let m = self.get_mod();
            while exp > 0 {
                if exp & 1 != 0 {
                    res *= base;
                    res %= m;
                }
                base *= base;
                base %= m;
                exp >>= 1;
            }
            Self::new(res, self.get_mod())
        }
        /// `a / b == a * b^(-1)` となる `b^(-1)` を求める
        pub fn inv(&self) -> i64 {
            let x = self.get().extended_gcd(&(self.get_mod() as i64)).x;
            compensated_rem(x, self.get_mod())
        }
    }
    impl Add<Self> for ModInt {
        type Output = Self;
        fn add(self, rhs: Self) -> Self::Output {
            let c = check_mod_eq(&self, &rhs);
            if !c.1 {
                panic!("modulo between two instance is different!",)
            }
            let r = self.get() + rhs.num;
            Self {
                num: if r >= self.get_mod() as i64 {
                    r - c.0.get() as i64
                } else {
                    r
                },
                _modulo: Modulo::Static(c.0),
            }
        }
    }
    impl AddAssign<Self> for ModInt {
        fn add_assign(&mut self, rhs: Self) {
            *self = *self + rhs;
        }
    }
    impl Sub<Self> for ModInt {
        type Output = Self;
        fn sub(self, rhs: Self) -> Self::Output {
            let c = check_mod_eq(&self, &rhs);
            if !c.1 {
                panic!("modulo between two instance is different!",)
            }
            let num = compensated_rem(self.get() - rhs.get(), c.0.get() as usize);
            Self {
                num,
                _modulo: Modulo::Static(c.0),
            }
        }
    }
    impl SubAssign<Self> for ModInt {
        fn sub_assign(&mut self, rhs: Self) {
            *self = *self - rhs;
        }
    }
    impl Mul<Self> for ModInt {
        type Output = Self;
        fn mul(self, rhs: Self) -> Self::Output {
            let c = check_mod_eq(&self, &rhs);
            if !c.1 {
                panic!("modulo between two instance is different!",)
            }
            let num = compensated_rem(self.get() * rhs.get(), c.0.get() as usize);
            Self {
                num,
                _modulo: Modulo::Static(c.0),
            }
        }
    }
    impl MulAssign<Self> for ModInt {
        fn mul_assign(&mut self, rhs: Self) {
            *self = *self * rhs
        }
    }
    impl Div<Self> for ModInt {
        type Output = Self;
        fn div(self, rhs: Self) -> Self::Output {
            let c = check_mod_eq(&self, &rhs);
            if !c.1 {
                panic!("modulo between two instance is different!",)
            }
            Self {
                num: self.get() * rhs.inv() % c.0.get() as i64,
                _modulo: Modulo::Static(c.0),
            }
        }
    }
    impl DivAssign<Self> for ModInt {
        fn div_assign(&mut self, rhs: Self) {
            *self = *self / rhs;
        }
    }
    impl Rem for ModInt {
        type Output = Self;
        fn rem(self, rhs: Self) -> Self::Output {
            let c = check_mod_eq(&self, &rhs);
            if !c.1 {
                panic!("modulo between two instance is different!",)
            }
            Self {
                num: self.num % rhs.num,
                _modulo: Modulo::Static(c.0),
            }
        }
    }
    impl RemAssign for ModInt {
        fn rem_assign(&mut self, rhs: Self) {
            *self = *self % rhs
        }
    }
    impl Zero for ModInt {
        fn zero() -> Self {
            ModInt {
                num: 0,
                _modulo: Modulo::Dynamic,
            }
        }
        fn is_zero(&self) -> bool {
            self.num == 0
        }
    }
    impl One for ModInt {
        fn one() -> Self {
            ModInt {
                num: 1,
                _modulo: Modulo::Dynamic,
            }
        }
        fn is_one(&self) -> bool {
            self.num == 1
        }
    }
    impl Num for ModInt {
        type FromStrRadixErr = ParseIntError;
        fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
            let num = str
                .chars()
                .rev()
                .enumerate()
                .map(|(i, b)| radix.pow(i as u32) as i64 * b.to_digit(radix).unwrap() as i64)
                .sum::<i64>();
            Ok(ModInt {
                num,
                _modulo: Modulo::Dynamic,
            })
        }
    }
    impl Pow<usize> for ModInt {
        type Output = Self;
        fn pow(self, exp: usize) -> Self::Output {
            self.pow_mod(exp)
        }
    }
    impl Factoriable for ModInt {
        fn falling(self, take: usize) -> Self {
            let mut res = Self::one();
            let mut c = self;
            for _ in 0..take {
                res *= c;
                c -= Self::one();
            }
            res
        }
        fn rising(self, take: usize) -> Self {
            let mut res = Self::one();
            let mut c = self;
            for _ in 0..take {
                res *= c;
                c += 1;
            }
            res
        }
    }
    macro_rules ! impl_ops_between_mint_and_primitive {($ ($ t : ty ) ,* ) => {$ (impl Add <$ t > for ModInt {type Output = Self ; fn add (self , rhs : $ t ) -> Self :: Output {self + Self :: new (rhs as i64 , self . get_mod () ) } } impl AddAssign <$ t > for ModInt {fn add_assign (& mut self , rhs : $ t ) {* self = * self + rhs ; } } impl Sub <$ t > for ModInt {type Output = Self ; fn sub (self , rhs : $ t ) -> Self :: Output {self - Self :: new (rhs as i64 , self . get_mod () ) } } impl SubAssign <$ t > for ModInt {fn sub_assign (& mut self , rhs : $ t ) {* self = * self - rhs ; } } impl Mul <$ t > for ModInt {type Output = Self ; fn mul (self , rhs : $ t ) -> Self :: Output {self * Self :: new (rhs as i64 , self . get_mod () ) } } impl MulAssign <$ t > for ModInt {fn mul_assign (& mut self , rhs : $ t ) {* self = * self * rhs ; } } impl Div <$ t > for ModInt {type Output = Self ; fn div (self , rhs : $ t ) -> Self :: Output {self / Self :: new (rhs as i64 , self . get_mod () ) } } impl DivAssign <$ t > for ModInt {fn div_assign (& mut self , rhs : $ t ) {* self = * self / rhs ; } } ) * } ; }
    impl_ops_between_mint_and_primitive!(usize, u8, u16, u32, u64, isize, i8, i16, i32, i64);
    pub trait PartialBinomialCoefficient {
        fn partial_binomial(&self, n: usize, k: usize) -> Option<ModInt>;
    }
    pub trait BinomialCoefficient: PartialBinomialCoefficient {
        /// `n C k`
        fn binomial(&self, n: usize, k: usize) -> ModInt {
            self.partial_binomial(n, k).unwrap()
        }
    }
    /// Binomial Coefficient Table with DP
    /// 二項係数を`O(1)`で計算するためのテーブル
    /// factrial = [1, 1, 2, 6, 24, 120, ...],
    /// `1 <= k <= n <= 10^7` 程度
    pub struct BCTDP {
        _modulo: NonZeroU32,
        factorial: Vec<ModInt>,
        inverse: Vec<ModInt>,
        factorial_inverse: Vec<ModInt>,
    }
    impl BCTDP {
        /// 初期化
        /// DPを用いて `O(n log m)`
        /// 割り算を用いるので `log m` がつく
        /// `1 <= k <= n <= 10^7` 程度
        pub fn new(n: usize, modulo: usize) -> BCTDP {
            let mut factorial = vec![ModInt::new(1, modulo), ModInt::new(1, modulo)];
            factorial.reserve_exact(n);
            let mut inverse = vec![ModInt::new(0, modulo), ModInt::new(1, modulo)];
            inverse.reserve_exact(n);
            let mut factorial_inverse = vec![ModInt::new(1, modulo), ModInt::new(1, modulo)];
            factorial_inverse.reserve_exact(n);
            for i in 2..=n {
                factorial.push(factorial[i - 1] * i);
                inverse.push(modulo.to_mint(modulo) - inverse[modulo % i] * (modulo / i));
                factorial_inverse.push(factorial_inverse[i - 1] * inverse[i]);
            }
            Self {
                _modulo: NonZeroU32::new(modulo as u32).unwrap(),
                factorial,
                inverse,
                factorial_inverse,
            }
        }
        pub fn get_mod(&self) -> usize {
            self._modulo.get() as usize
        }
        pub fn factorial(&self, n: usize) -> ModInt {
            self.factorial[n]
        }
        pub fn factorial_inverse(&self, n: usize) -> ModInt {
            self.factorial_inverse[n]
        }
        /// `n` の mod self._modulo における逆元
        pub fn inv(&self, n: usize) -> ModInt {
            self.inverse[n]
        }
    }
    impl PartialBinomialCoefficient for BCTDP {
        fn partial_binomial(&self, n: usize, k: usize) -> Option<ModInt> {
            Some(if n < k {
                ModInt::zero()
            } else {
                self.factorial[n] * self.factorial_inverse[k] * self.factorial_inverse[n - k]
            })
        }
    }
    impl BinomialCoefficient for BCTDP {}
    /// `n` が固定値のときに有効
    /// `(n(固定値), mod, _[i] = n C i)`
    /// 初期化: `O(n)`
    /// `1 <= n <= 10^9 && 1 <= k <= 10^7` 程度
    pub struct BCTholdN(usize, NonZeroU32, Vec<ModInt>);
    impl BCTholdN {
        pub fn new(mut n: usize, m: usize) -> Self {
            let size = n;
            let mut c = vec![ModInt::new(1, m), ModInt::new(n, m)];
            c.reserve_exact(n + 1);
            for i in 2..=n {
                n -= 1;
                let prev = *c.last().unwrap();
                c.push(prev * n / i);
            }
            Self(size, NonZeroU32::new(m as u32).unwrap(), c)
        }
    }
    impl PartialBinomialCoefficient for BCTholdN {
        /// #Panic
        /// self.0 == _n でないとき
        fn partial_binomial(&self, _n: usize, k: usize) -> Option<ModInt> {
            if _n != self.0 {
                None
            } else {
                Some(self.2[k])
            }
        }
    }
    impl BinomialCoefficient for BCTholdN {}
    #[test]
    fn hold_n_test() {
        let tbl = BCTholdN::new(10, 1000000007);
        assert_eq!(tbl.partial_binomial(10, 2).unwrap().get(), 45);
        assert_eq!(tbl.partial_binomial(10, 10).unwrap().get(), 1);
    }
    /// `n, k` の2変数についての `n C k` の表を作る
    /// `1 <= k <= n <= 2000` 程度
    pub struct BCTSmallNK {
        n: usize,
        _modulo: NonZeroU32,
        dp: Vec<Vec<ModInt>>,
    }
    impl BCTSmallNK {
        pub fn new(n: usize, modulo: usize) -> Self {
            let mut dp = vec![vec![ModInt::new(0, modulo); n + 1]; n + 1];
            dp[0][0] = 1.to_mint(modulo);
            for i in 1..n {
                dp[i][0] = 1.to_mint(modulo);
                for j in 1..n {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
            Self {
                n,
                _modulo: NonZeroU32::new(modulo as u32).unwrap(),
                dp,
            }
        }
        pub fn size(&self) -> usize {
            self.n
        }
        pub fn get_mod(&self) -> usize {
            self._modulo.get() as usize
        }
    }
    impl PartialBinomialCoefficient for BCTSmallNK {
        fn partial_binomial(&self, n: usize, k: usize) -> Option<ModInt> {
            if n > self.size() || k > self.size() {
                panic!("n or k is too large, compere to dp table!",)
            }
            Some(self.dp[n][k])
        }
    }
    impl BinomialCoefficient for BCTSmallNK {}
    pub trait Factoriable: Sized + NumOps + NumAssignOps + Copy + TryInto<usize> {
        fn falling(self, take: usize) -> Self;
        fn rising(self, take: usize) -> Self;
        fn factorial(self) -> Self {
            self.falling(self.try_into().ok().unwrap())
        }
    }
    macro_rules ! impl_factorialbe {($ ($ t : ty ) ,* ) => {$ (impl Factoriable for $ t {fn falling (self , take : usize ) -> Self {let mut res = Self :: one () ; let mut c = self ; for _ in 0 .. take {res *= c ; c -= Self :: one () ; } res } fn rising (self , take : usize ) -> Self {let mut res = Self :: one () ; let mut c = self ; for _ in 0 .. take {res *= c ; c += 1 ; } res } } ) * } ; }
    impl_factorialbe!(usize, u8, u16, u32, u64, isize, i8, i16, i32, i64);
    /// `n P k` を `O(k)` で
    /// 内部はfallingをラップしているだけ
    pub fn permutation<T: Factoriable>(n: T, k: usize) -> T {
        n.falling(k)
    }
    pub fn permutation_with_table(table: &BCTDP, n: usize, k: usize) -> ModInt {
        if k > n {
            ModInt::new(0, table.get_mod())
        } else {
            table.factorial(n) * table.factorial_inverse(n - k)
        }
    }
    pub fn combination(n: ModInt, k: usize) -> ModInt {
        if k > n.get() as usize {}
        permutation(n, k) / k.factorial()
    }
    pub fn combination_with_table<T: BinomialCoefficient>(table: &T, n: usize, k: usize) -> ModInt {
        table.binomial(n, k)
    }
}

#[derive(Clone)]
pub struct DelayedSegmentTree<'a, T: Monoid, E: Monoid> {
    /// length of tree's leaves
    len: usize,
    /// length of whole vec
    size: usize,
    effect: &'a dyn Fn(T, E) -> T,
    segment: Vec<T>,
    lazy: Vec<E>,
}
fn childrens_idx(n: usize) -> (usize, usize) {
    (n * 2 + 1, n * 2 + 2)
}
impl<'a, T: Monoid + Clone + Copy, E: Monoid + Clone + Copy> DelayedSegmentTree<'a, T, E> {
    pub fn new<I: Into<T> + Copy>(v: &[I], effect: &'a dyn Fn(T, E) -> T) -> Self {
        let n = v.len();
        let len = n.next_power_of_two();
        let size = 2 * len - 1;
        let mut segment = vec![T::identity(); size];
        let lazy = vec![E::identity(); size];
        for i in (0..size).rev() {
            if i >= len - 1 {
                if i + 1 - len < n {
                    segment[i] = (v[i + 1 - len]).into();
                } else {
                    continue;
                }
            } else {
                let (left, right) = childrens_idx(i);
                segment[i] = T::op(&segment[left], &segment[right]);
            }
        }
        Self {
            len,
            size,
            effect,
            segment,
            lazy,
        }
    }
    /// number of LEAVES in tree
    pub fn len(&self) -> usize {
        self.len
    }
    /// length of vector
    pub fn size(&self) -> usize {
        self.size
    }
    /// `i`番目の葉の参照をとる
    pub fn get(&self, i: usize) -> Option<&T> {
        self.segment.get(self.size - self.len + i)
    }
    /// `i`番目の葉の可変参照をとる
    /// # Unsafe
    /// 葉の部分は変更されうるけれど、その親要素へ変更が伝達されない
    /// update()を使うこと
    pub unsafe fn get_mut(&mut self, i: usize) -> Option<&mut T> {
        let size = self.size();
        let len = self.len();
        self.segment.get_mut(size - len + i)
    }
    fn eval(&mut self, i: usize) {
        if self.lazy[i] == E::identity() {
            return;
        }
        if i < self.len() - 1 {
            let (left, right) = childrens_idx(i);
            self.lazy[left] = E::op(&self.lazy[left], &self.lazy[i]);
            self.lazy[right] = E::op(&self.lazy[right], &self.lazy[i]);
        }
        let f = self.effect;
        self.segment[i] = f(self.segment[i], self.lazy[i]);
        self.lazy[i] = E::identity();
    }
    pub fn update_range(&mut self, from: usize, to: usize, x: E) {
        self.update_range_inner(from, to, 0, self.len(), 0, x);
    }
    fn update_range_inner(
        &mut self,
        from: usize,
        to: usize,
        l_bound: usize,
        r_bound: usize,
        k: usize,
        x: E,
    ) {
        self.eval(k);
        if from >= r_bound || to <= l_bound {
            return;
        }
        if from <= l_bound && to >= r_bound {
            self.lazy[k] = E::op(&self.lazy[k], &x);
            self.eval(k);
            return;
        }
        let sep = (l_bound + r_bound) / 2;
        let (left, right) = childrens_idx(k);
        self.update_range_inner(from, to, l_bound, sep, left, x);
        self.update_range_inner(from, to, sep, r_bound, right, x);
        self.segment[k] = T::op(&self.segment[left], &self.segment[right]);
    }
    /// 区間、`[from..to)`を指定の`Monoid`でfoldした演算結果
    pub fn range(&mut self, from: usize, to: usize) -> T {
        self.range_inner(from, to, 0, self.len(), 0)
    }
    fn range_inner(
        &mut self,
        from: usize,
        to: usize,
        l_bound: usize,
        r_bound: usize,
        k: usize,
    ) -> T {
        self.eval(k);
        if from <= l_bound && to >= r_bound {
            self.segment[k]
        } else if from >= r_bound || to <= l_bound {
            T::identity()
        } else {
            let sep = (l_bound + r_bound) / 2;
            T::op(
                &self.range_inner(from, to, l_bound, sep, 2 * k + 1),
                &self.range_inner(from, to, sep, r_bound, 2 * k + 2),
            )
        }
    }
}

/// 単位元が定義される `T -> T -> T`型の演算
pub trait Monoid: Sized + PartialEq {
    fn identity() -> Self;
    fn op(x: &Self, y: &Self) -> Self;
    fn fold(v: &[Self]) -> Self {
        v.iter().fold(Self::identity(), |a, b| Self::op(&a, b))
    }
}
/// Monoidトレイトの自動実装マクロ
/// 一行目にモノイド名、
/// 二行目に単位元
/// 三行目に`2引数を取って、同型の演算結果を返すクロージャを渡す
/// ```example
/// monoid_def! {
///     Max<usize>,
///     std::usize::MIN,
///     |x: usize, y: usize| x.max(y)
/// }
/// ```
#[macro_export]
macro_rules ! monoid_def {{$ M : ident <$ t : ty >, $ id : expr , $ me : expr } => {# [derive (Debug , Clone , Copy , PartialEq ) ] pub struct $ M ($ t ) ; impl Monoid for $ M {fn identity () -> Self {$ M ($ id ) } fn op (x : & Self , y : & Self ) -> Self {let f = $ me ; $ M (f (x . 0 , y . 0 ) ) } } impl Into <$ M > for $ t {fn into (self ) -> $ M {$ M (self ) } } } ; }

monoid_def! {
    Sum<ModInt>,
    ModInt::new(0, MOD99_),
    |x, y| x + y
}

monoid_def! {
    Plus<ModInt>,
    ModInt::new(0, MOD99_),
    |x, y| x + y
}
// #[fastout]
fn main() {
    input! {
        n: usize, k: usize,
        lr: [(usize, usize); k]
    }

    let s = lr
        .iter()
        .map(|&(l, r)| (l..=r).collect_vec())
        .flatten()
        .sorted()
        .collect_vec();

    let mut v = vec![ModInt::new(0usize, MOD99_); n];
    v[0] += 1;
    let mut dp = DelayedSegmentTree::<Sum, Plus>::new(&v, &|t: Sum, e: Plus| Sum(t.0 + e.0));

    for i in 0..n {
        let d = dp.range(i, i + 1).0;
        for &(l, r) in lr.iter() {
            dp.update_range(i + l, i + r + 1, Plus(d));
        }
    }

    // for i in 0..n {
        // dbg!(dp.range(i, i + 1).0);
    // }

    let ans = dp.range(n - 1, n).0.get();
    vis!(ans);
}


Measured memory_bytes: 23440