#![allow(non_snake_case, unused_must_use, unused_imports)] use std::io::{self, prelude::*}; use std::{fmt::*, ops::*}; const MOD: u32 = 998244353; fn main() { let (stdin, stdout) = (io::read_to_string(io::stdin()).unwrap(), io::stdout()); let (mut stdin, mut buffer) = (stdin.split_whitespace(), io::BufWriter::new(stdout.lock())); macro_rules! input { ($t: tt, $n: expr) => { (0..$n).map(|_| input!($t)).collect::>() }; (Chars) => { input!(String).chars().collect::>() }; (Usize1) => { stdin.next().unwrap().parse::().unwrap() - 1 }; ($t: ty) => { stdin.next().unwrap().parse::<$t>().unwrap() }; } let N = input!(usize); let M = input!(usize); let K = input!(usize); let mut A = input!(usize, N); A.sort(); let mut left = vec![0; N]; let mut right = vec![N - 1; N]; for i in 0..N { // left if A[i] - A[0] > K { let mut ok = i; let mut ng = 0; while ok - ng > 1 { let mid = (ok + ng) / 2; if A[i] - A[mid] <= K { ok = mid; } else { ng = mid; } } left[i] = ok; } // right if A[N - 1] - A[i] > K { let mut ok = i; let mut ng = N - 1; while ng - ok > 1 { let mid = (ok + ng) / 2; if A[mid] - A[i] <= K { ok = mid; } else { ng = mid; } } right[i] = ok; } } let mut dp = vec![ModInt::(1); N]; for _ in 0..M - 1 { let mut dp_nxt = vec![ModInt::(0); N]; let cs = CumulativeSum::from(&dp); for i in 0..N { dp_nxt[i] = cs.sum(left[i]..=right[i]); } dp = dp_nxt; } let mut ans = ModInt::(0); for v in dp { ans += v; } writeln!(buffer, "{}", ans); } #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, Default)] pub struct ModInt(u32); impl ModInt

{ pub fn from_raw(value: u32) -> Self { assert!(value < P); Self(value) } pub fn pow(&self, mut x: u32) -> Self { let mut a = *self; let mut r = Self::from_raw(1); while x > 0 { if x & 1 == 1 { r *= a; } a *= a; x >>= 1; } r } pub fn inv(&self) -> Self { self.pow(P - 2) } } impl Add for ModInt

{ type Output = Self; fn add(self, rhs: Self) -> Self::Output { Self((self.0 + rhs.0) % P) } } impl Sub for ModInt

{ type Output = Self; fn sub(self, rhs: Self) -> Self::Output { Self((P + self.0 - rhs.0) % P) } } impl 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 Div for ModInt

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

{ fn add_assign(&mut self, rhs: Self) { self.0 += rhs.0; self.0 %= P; } } impl SubAssign for ModInt

{ fn sub_assign(&mut self, rhs: Self) { self.0 += P - rhs.0; self.0 %= P; } } impl MulAssign for ModInt

{ fn mul_assign(&mut self, rhs: Self) { *self = self.clone() * rhs; } } impl DivAssign for ModInt

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

{ type Output = Self; fn neg(self) -> Self::Output { Self((P - self.0) % P) } } impl Display for ModInt

{ fn fmt(&self, f: &mut Formatter<'_>) -> Result { write!(f, "{}", self.0) } } macro_rules! impl_op_for_modint { ($($t: ty), *) => { $( impl From<$t> for ModInt

{ fn from(value: $t) -> Self { Self((P as $t + value % P as $t) as u32 % P) } } impl Add<$t> for ModInt

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

; fn add(self, rhs: ModInt

) -> Self::Output { Self::Output::from(self) + rhs } } impl Sub<$t> for ModInt

{ type Output = Self; fn sub(self, rhs: $t) -> Self::Output { self - Self::from(rhs) } } impl Sub> for $t { type Output = ModInt

; fn sub(self, rhs: ModInt

) -> Self::Output { Self::Output::from(self) - rhs } } impl Mul<$t> for ModInt

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

; fn mul(self, rhs: ModInt

) -> Self::Output { Self::Output::from(self) * rhs } } impl Div<$t> for ModInt

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

; fn div(self, rhs: ModInt

) -> Self::Output { Self::Output::from(self) / rhs } } impl AddAssign<$t> for ModInt

{ fn add_assign(&mut self, rhs: $t) { *self += Self::from(rhs) } } impl SubAssign<$t> for ModInt

{ fn sub_assign(&mut self, rhs: $t) { *self -= Self::from(rhs) } } impl MulAssign<$t> for ModInt

{ fn mul_assign(&mut self, rhs: $t) { *self *= Self::from(rhs) } } impl DivAssign<$t> for ModInt

{ fn div_assign(&mut self, rhs: $t) { *self /= Self::from(rhs) } } )* }; } impl_op_for_modint!(usize, isize, u64, i64, u32, i32); pub struct CumulativeSum { size: usize, prefix_sum: Vec, } impl + Default + Clone + Copy> CumulativeSum { pub fn from(array: &[T]) -> Self { let size = array.len(); let mut prefix_sum = vec![T::default(); size + 1]; for i in 0..size { prefix_sum[i + 1] = prefix_sum[i] + array[i]; } Self { size, prefix_sum } } pub fn prefix_sum(&self, i: usize) -> T { self.prefix_sum[i + 1] } } impl + std::ops::Sub + Default + Clone + Copy> CumulativeSum { 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.size - 1, }; if left == 0 { return self.prefix_sum(right); } else { return self.prefix_sum(right) - self.prefix_sum(left - 1); } } }