/* ><> 魚fishに癒されたい(><) ><> >><> ><> ><> ><> ><> ><> >>><>><><<> ><>><> ><> ><> ><> ><> >><<<>>> ><> ><> ><> >><> ^<> v ><> ><> ><> ><> >><>> ><> ><> ^ ><> >><><> ><> ><> v ><> ><> <>><< <>< ><> >>>>><<<<<<>>>>>>> >< >><<>>> ><> ><> >><>> <>< ><> ><> ><> >> > <> ><> ><> >>><<<>>>>>> ><> ><> ><> >< ><> ><> ><><><>>>>><><>>>> >><> ><> ><> ><> <<> <>< >><>> ><> ><> ><> ><> ><> >< (>< ><) ><> ><>> ^ <> ><> <>< ><> ><> ><> <<<><> ><> <>< ><> v ><> <>< ><> ><> ><> ><> ><> ><> ><><> ><> ><> >><<><>><>>><> ><>> >><>> */ #[allow(unused_imports)] use std::{ convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,}, fs::File, hash::{Hash, Hasher, BuildHasherDefault}, iter::{Product, Sum}, marker::PhantomData, ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, RangeBounds}, str::FromStr, sync::{atomic::{self, AtomicU32, AtomicU64}, Once}, collections::{*, btree_set::Range, btree_map::Range as BTreeRange}, mem::{swap}, cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd}, thread::LocalKey, f64::consts::PI, time::Instant, cell::RefCell, io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write}, }; pub trait SortD{ fn sort_d(&mut self); } impl SortD for Vec{ fn sort_d(&mut self) { self.sort_by(|u, v| v.cmp(&u)); } } pub trait Mx{fn max(&self, rhs: Self)->Self;} impl Mx for f64{ fn max(&self, rhs: Self)->Self{if *self < rhs{ rhs } else { *self } }} pub trait Mi{ fn min(&self, rhs: Self)->Self; } impl Mi for f64{ fn min(&self, rhs: Self)->Self{ if *self > rhs{ rhs } else { *self } } } #[inline(always)] pub fn gcd(mut a: i64, mut b: i64)->i64{if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros(); a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a>x;}a << l1.min(l2)} pub fn factorial_i64(n: usize)->(Vec, Vec){ let mut res = vec![1; n+1];let mut inv = vec![1; n+1];for i in 0..n{ res[i+1] = (res[i]*(i+1)as i64)%MOD; } inv[n] = mod_inverse(res[n], MOD);for i in (0..n).rev(){ inv[i] = inv[i+1]*(i+1) as i64%MOD; }(res, inv) } pub fn floor(a:i64, b:i64)->i64{let res=(a%b+b)%b;(a-res)/b} pub fn modulo(a: i64, b: i64)->i64{(a%b+b)%b} pub fn extended_gcd(a:i64,b:i64)->(i64,i64,i64) {if b==0{(a,1,0)}else{let(g,x,y)=extended_gcd(b,a%b);(g,y,x-floor(a,b)*y)}} pub fn mod_inverse(a:i64,m:i64)->i64{let(_,x,_) =extended_gcd(a,m);(x%m+m)%m} pub fn comb(a: i64, b: i64, f: &Vec<(i64, i64)>)->i64{ if aVec<(i64, i64)>{ let mut f=vec![(1i64,1i64),(1, 1)];let mut z = 1i64; let mut inv = vec![0; x as usize+10];inv[1] = 1; for i in 2..x+1{z=(z*i)%MOD; let w=(MOD-inv[(MOD%i)as usize]*(MOD/i)%MOD)%MOD; inv[i as usize] = w; f.push((z, (f[i as usize-1].1*w)%MOD));}return f;} pub fn fast_mod_pow(mut x: i64,p: usize, m: i64)->i64{ x %= m; let mut res=1;let mut t=x;let mut z=p;while z > 0{ if z%2==1{res = (res*t)%m;}t = (t*t)%m;z /= 2; }res} pub fn vec_out(v: Vec) where T: ToString{ println!("{}", v.iter().map(|x| x.to_string()).collect::>().join(" ")); } pub fn one_add_out(v: Vec){println!("{}", v.iter().map(|x| (x+1).to_string()).collect::>().join(" "));} pub trait Chmax{ fn chmax(&mut self, rhs: Self); } impl Chmax for i64{ fn chmax(&mut self, rhs: Self) { *self = (*self).max(rhs) } } impl Chmax for i32{ fn chmax(&mut self, rhs: Self) { *self = (*self).max(rhs) } } impl Chmax for f64{ fn chmax(&mut self, rhs: Self) { *self = (*self).max(rhs) } } impl Chmax for usize{ fn chmax(&mut self, rhs: Self) { *self = (*self).max(rhs) } } pub trait Chmin { fn chmin(&mut self, rhs: Self); } impl Chmin for i128{ fn chmin(&mut self, rhs: Self) { *self = (*self).min(rhs) } } impl Chmin for i64{ fn chmin(&mut self, rhs: Self) { *self = (*self).min(rhs) } } impl Chmin for i32{ fn chmin(&mut self, rhs: Self) { *self = (*self).min(rhs) } } impl Chmin for f64{ fn chmin(&mut self, rhs: Self) { *self = (*self).min(rhs) } } impl Chmin for usize{ fn chmin(&mut self, rhs: Self) { *self = (*self).min(rhs) } } #[derive(Debug, Clone)] pub struct Counter{ c: usize, map: BTreeMap, } impl Counter{ pub fn new()->Self{ Counter{ c: 0, map: BTreeMap::new(), } } #[inline(always)] pub fn range(&self, range: R)->BTreeRange<'_, T, usize> where R: RangeBounds{ self.map.range(range) } #[inline(always)] pub fn mi(&self)->Option{ if let Some((x, _)) = self.range(..).next(){ Some(*x) } else { None } } #[inline(always)] pub fn mx(&self)->Option{ if let Some((x, _)) = self.range(..).next_back(){ Some(*x) } else { None } } #[inline(always)] pub fn one_add(&mut self, x: T){ *self.map.entry(x).or_insert(0) += 1; self.c += 1; } #[inline(always)] pub fn one_sub(&mut self, x: T){ if !self.map.contains_key(&x){return} let e = self.map.entry(x).or_insert(0); *e = e.saturating_sub(1); if self.map[&x] <= 0{ self.map.remove(&x); } self.c = self.c.saturating_sub(1); } #[inline(always)] pub fn one_update(&mut self, x: T, y: T){ self.one_sub(x); self.one_add(y); } #[inline(always)] pub fn del(&mut self, x: T){ self.c = self.c.saturating_sub(*self.map.get(&x).unwrap_or(&0)); self.map.remove(&x); } #[inline(always)] pub fn add(&mut self, x: T, c: usize){ *self.map.entry(x).or_insert(0) += c; self.c += c; } #[inline(always)] pub fn sub(&mut self, x: T, c: usize){ let e = self.map.entry(x).or_insert(0); *e = e.saturating_sub(c); if self.map[&x] == 0{ self.map.remove(&x); } self.c = self.c.saturating_sub(c); } #[inline(always)] pub fn include(&self, x: T)->bool{ self.map.contains_key(&x) } #[inline(always)] pub fn cnt(&self, x: T)->usize{ *self.map.get(&x).unwrap_or(&0) } #[inline(always)] pub fn is_empty(&self)->bool{ self.map.is_empty() } #[inline(always)] pub fn len(&self)->usize{ self.map.len() } #[inline(always)] pub fn clear(&mut self){ self.map.clear(); self.c = 0; } #[inline(always)] pub fn merge(&mut self, rhs: &mut Counter){ if self.len() < rhs.len(){ swap(self, rhs); } for (&k, &v) in rhs.map.iter(){ self.add(k, v); } rhs.clear(); } } const MASK: usize = 63; const BN: usize = 64; const BB: usize = 6; #[derive(Clone, Debug)] pub struct BitSet{ data: Vec, } impl PartialEq<&BitSet> for BitSet { fn eq(&self, other: &&BitSet) -> bool { self==other } } impl BitSet { #[inline] pub fn new(cap: usize) -> Self { BitSet{ data: vec![0; (cap+MASK)>>BB], } } #[inline] pub fn build(base: Vec) -> Self { BitSet { data: base } } #[inline] pub fn set(&mut self, p: usize, f: bool){ if f{ self.data[p>>BB] |= 1<<(p&MASK); } else { self.data[p>>BB] &= !(1<<(p&MASK)); } } #[inline] pub fn flip(&mut self, p: usize){ self.data[p>>BB] ^= 1<<(p&MASK) } #[inline(always)] pub fn len(&self) -> usize { self.data.len() } #[inline(always)] pub fn get(&self, p: usize) -> bool { self.data[p>>BB] & (1 << (p&MASK)) != 0 } #[inline] pub fn and(&self, rhs: &Self) -> Self { if self.len() < rhs.len() { let mut res = rhs.clone(); for (i, &x) in self.data.iter().enumerate(){ res.data[i] &= x; } res } else { let mut res = self.clone(); for (i, &x) in rhs.data.iter().enumerate(){ res.data[i] &= x; } res } } #[inline] pub fn or(&self, rhs: &Self) -> Self{ if self.len() < rhs.len() { let mut res = rhs.clone(); for (i, &x) in self.data.iter().enumerate(){ res.data[i] |= x; } res } else { let mut res = self.clone(); for (i, &x) in rhs.data.iter().enumerate(){ res.data[i] |= x; } res } } #[inline] pub fn xor(&self, rhs: &Self) -> Self { if self.len() < rhs.len() { let mut res = rhs.clone(); for (i, &x) in self.data.iter().enumerate(){ res.data[i] ^= x; } res } else { let mut res = self.clone(); for (i, &x) in rhs.data.iter().enumerate(){ res.data[i] ^= x; } res } } // 配列上の左シフトです #[inline] pub fn get_shift_left(&self, k: usize) -> Self { let b = k>>BB; let r = k&MASK; let n = self.data.len(); let mut res = vec![0; n]; for i in 0..n.max(b)-b{ res[i+b] |= self.data[i] << r; if r > 0 && i+b+1 < n { res[i+b+1] |= self.data[i] >> (BN-r); } } Self::build(res) } #[inline] pub fn get_shift_right(&self, k: usize) -> Self { let b = k>>BB; let r = k&MASK; let n = self.data.len(); let mut res = vec![0; n]; for i in b..n{ res[i-b] |= self.data[i] >> r; if r > 0 && b+1 <= i { res[i-b-1] |= self.data[i] << (BN-r); } } Self::build(res) } #[inline] pub fn count_ones(&self) -> usize { self.data.iter().map(|x| x.count_ones() as usize).sum::() } #[inline] pub fn count_zeros(&self) -> usize { self.data.iter().map(|x| x.count_zeros() as usize).sum::() } } #[allow(unused)] mod fxhash{ use std::hash::BuildHasherDefault; #[derive(Default)] pub struct FxHasher{ pub hash: u64, } impl std::hash::Hasher for FxHasher{ #[inline(always)] fn finish(&self) -> u64 { self.hash } #[inline(always)] fn write(&mut self, bytes: &[u8]) { let mut h = self.hash; for &b in bytes{ h = h.rotate_left(5)^(b as u64); h = h.wrapping_mul(0x517cc1b727220a95); } self.hash = h; } } pub type FxBuildHasher = BuildHasherDefault; pub type FxMap = std::collections::HashMap; pub type FxSet = std::collections::HashSet; } #[allow(unused_imports)] use fxhash::{FxSet, FxMap, FxBuildHasher}; #[allow(unused_imports)] use proconio::{input, input_interactive, marker::{*}, fastout}; /* #[allow(unused_imports)] use rustc_hash::FxHasher; #[allow(dead_code)] type FxMap = HashMap>; #[allow(dead_code)] type FxSet = HashSet>; #[allow(unused_imports)] use rand::{Rng, seq::SliceRandom, prelude::*}; #[allow(unused_imports)] use itertools::Itertools; #[allow(unused_imports)] use ordered_float::OrderedFloat; #[allow(unused_imports)] use num_bigint::BigInt; #[allow(unused_imports)] use ac_library::{*, ModInt1000000007 as mint}; */ #[allow(dead_code)] //type MI = StaticModInt;pub fn factorial_mint(n: usize)->(Vec, Vec){ let mut res = vec![mint::new(1); n+1];let mut inv = vec![mint::new(1); n+1];for i in 0..n{res[i+1] = res[i]*(i+1);}inv[n] = mint::new(1)/res[n];for i in (0..n).rev(){inv[i] = inv[i+1]*(i+1);}(res, inv)}pub fn cm(a: usize, b: usize, mf: &(Vec, Vec))->MI{if a(usize, usize){match c{b'U'=>(!0,0),b'D'=>(1,0),b'L'=>(0,!0),b'R'=>(0,1),_=>unreachable!()}} #[allow(dead_code)] pub fn c2d_i64(c: u8)->(i64, i64){match c{b'U'=>(-1,0),b'D'=>(1,0),b'L'=>(0,-1),b'R'=>(0,1),_=>unreachable!()}} #[allow(dead_code)] const D2: [(usize, usize); 8] = [(1, 0), (1, 1), (0, 1), (!0, 1), (!0, 0), (!0, !0), (0, !0), (1, !0)]; //#[fastout] fn main() { let t = 1; //input!{t: usize,} for _ in 0..t{ solve(); } } //#[fastout] fn solve(){ input!{ n: usize, m: usize, k: i32, mut a: [i32; n], } a.sort(); let mut left = vec![0; n]; let mut right = vec![0; n]; let mut r = 0; for i in 0..n{ while r < n && a[r] <= a[i]+k{ r += 1; } right[i] = r; } let mut l = n; for i in (0..n).rev(){ while l > 0 && a[i] <= a[l-1]+k{ l -= 1; } left[i] = l; } let mut dp = vec![1; n]; for _ in 0..m-1{ let mut ndp = vec![0; n]; let mut res = 0; let (mut lp, mut rp) = (0, 0); for (i, (&l, &r)) in left.iter().zip(&right).enumerate(){ while rp < r{ res = (res+dp[rp])%MOD; rp += 1; } while lp < l{ res = (res+MOD-dp[lp])%MOD; lp += 1; } ndp[i] = res; } dp = ndp; } let mut ac = 0; for &v in &dp{ ac = (ac+v)%MOD; } println!("{}", ac); }