#![allow(non_snake_case, unused_imports)] use proconio::{fastout, input, marker::*}; type MInt = ModInt<998244353>; #[fastout] fn main() { input! { N: usize, K: usize, } let mut dp = BinaryIndexedTree::new(N + 1); dp.add(0, MInt::from_raw(1)); for i in K..=N { let s = dp.sum(0..=i - K); dp.add(i, s); } let ans = dp.sum(0..=N); println!("{}", ans); } pub struct BinaryIndexedTree { tree: Vec, } impl> BinaryIndexedTree { /// self = [0; size] pub fn new(size: usize) -> Self { return Self { tree: vec![T::default(); size + 1], }; } /// self[i] <- self[i] + w pub fn add(&mut self, i: usize, w: T) { self._add(i + 1, w); } /// return Σ_{j ∈ [0, i]} self[j] pub fn prefix_sum(&self, i: usize) -> T { self._sum(i + 1) } /// return Σ_{j ∈ range} self[j] pub fn sum>(&self, range: R) -> T { let left = match range.start_bound() { std::ops::Bound::Included(&l) => l, std::ops::Bound::Excluded(&l) => l + 1, std::ops::Bound::Unbounded => 0, }; let right = match range.end_bound() { std::ops::Bound::Included(&r) => r, std::ops::Bound::Excluded(&r) => r - 1, std::ops::Bound::Unbounded => self.tree.len() - 2, }; if left == 0 { return self.prefix_sum(right); } else { return self.prefix_sum(right) - self.prefix_sum(left - 1); } } fn _add(&mut self, mut i: usize, w: T) { while i < self.tree.len() { self.tree[i] += w; i += i & i.wrapping_neg(); } } fn _sum(&self, mut i: usize) -> T { let mut ret = T::default(); while i > 0 { ret += self.tree[i]; i -= i & i.wrapping_neg(); } return ret; } } #[derive(Clone, Copy, PartialEq, Eq, Debug, Default)] pub struct ModInt(u32); impl ModInt

{ pub fn value(&self) -> u32 { return self.0; } pub fn new() -> Self { Self(0) } pub fn from_raw(value: u32) -> Self { Self(value) } pub fn inv(&self) -> Self { self.pow(P as u64 - 2) } pub fn pow(&self, mut x: u64) -> Self { let mut a = self.clone(); let mut r = Self::from_raw(1); while x > 0 { if x & 1 == 1 { r *= a; } a *= a; x >>= 1; } r } } macro_rules! impl_to_integer_types { ($($t: ty), *) => { $( impl From<$t> for ModInt

{ fn from(value: $t) -> Self { let v = ((value % (P as $t)) + P as $t) as u32; Self(if v >= P { v - P } else { v }) } } impl std::ops::Add<$t> for ModInt

{ type Output = Self; fn add(self, rhs: $t) -> Self::Output { self + ModInt::

::from(rhs) } } impl std::ops::AddAssign<$t> for ModInt

{ fn add_assign(&mut self, rhs: $t) { self.0 += ModInt::

::from(rhs).0; if self.0 >= P { self.0 -= P; } } } impl std::ops::Sub<$t> for ModInt

{ type Output = Self; fn sub(self, rhs: $t) -> Self::Output { self - ModInt::

::from(rhs) } } impl std::ops::SubAssign<$t> for ModInt

{ fn sub_assign(&mut self, rhs: $t) { let m = ModInt::

::from(rhs); if self.0 >= m.0 { self.0 -= m.0; } else { self.0 += P - m.0; } } } impl std::ops::Mul<$t> for ModInt

{ type Output = Self; fn mul(self, rhs: $t) -> Self::Output { self * ModInt::

::from(rhs) } } impl std::ops::MulAssign<$t> for ModInt

{ fn mul_assign(&mut self, rhs: $t) { let r = self.0 as u64; self.0 = ((r * ModInt::

::from(rhs).0 as u64) % P as u64) as u32; } } impl std::ops::Div<$t> for ModInt

{ type Output = Self; fn div(self, rhs: $t) -> Self::Output { self / ModInt::

::from(rhs) } } impl std::ops::DivAssign<$t> for ModInt

{ fn div_assign(&mut self, rhs: $t) { *self *= ModInt::

::from(rhs).inv(); } } )* }; } impl_to_integer_types!(usize, isize, u64, i64, u32, i32); impl std::ops::Add for ModInt

{ type Output = Self; fn add(self, rhs: Self) -> Self::Output { let r = self.0 + rhs.0; Self(if r >= P { r - P } else { r }) } } impl std::ops::AddAssign for ModInt

{ fn add_assign(&mut self, rhs: Self) { self.0 += rhs.0; if self.0 >= P { self.0 -= P; } } } impl std::ops::Sub for ModInt

{ type Output = Self; fn sub(self, rhs: Self) -> Self::Output { Self(if self.0 >= rhs.0 { self.0 - rhs.0 } else { P + self.0 - rhs.0 }) } } impl std::ops::SubAssign for ModInt

{ fn sub_assign(&mut self, rhs: Self) { if self.0 >= rhs.0 { self.0 -= rhs.0; } else { self.0 += P - rhs.0; } } } impl std::ops::Mul for ModInt

{ type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Self(((self.0 as u64 * rhs.0 as u64) % P as u64) as u32) } } impl std::ops::MulAssign for ModInt

{ fn mul_assign(&mut self, rhs: Self) { let r = self.0 as u64; self.0 = ((r * rhs.0 as u64) % P as u64) as u32; } } impl std::ops::Div for ModInt

{ type Output = Self; fn div(self, rhs: Self) -> Self::Output { self * rhs.inv() } } impl std::ops::DivAssign for ModInt

{ fn div_assign(&mut self, rhs: Self) { *self *= rhs.inv(); } } impl std::fmt::Display for ModInt

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } }