#include #include using namespace std; using namespace atcoder; #define ll long long #define rep(i,a,b) for(int i=(a);i<(b);i++) #define repl(i,a,b) for(ll i=(a);i<(b);i++) #define all(a) (a).begin(),(a).end() template bool chmin(T &a,T b){if(a>b){a=b;return true;} return false;} template bool chmax(T &a,T b){if(a> n >> m >> k; vector a(n); rep(i,0,n) cin >> a[i]; vector left(n),right(n); sort(all(a)); rep(i,0,n){ left[i]=lower_bound(all(a),a[i]-k)-a.begin(); right[i]=upper_bound(all(a),a[i]+k)-a.begin(); } vector dp(n+1); rep(i,0,n) dp[i]=1; vector c(n+1); rep(j,1,m){ rep(i,0,n){ c[left[i]]+=dp[i]; c[right[i]]-=dp[i]; } rep(i,0,n+1){ dp[i]=c[i]; c[i]=0; } rep(i,0,n) dp[i+1]+=dp[i]; } mint ans=0; rep(i,0,n) ans+=dp[i]; cout << ans.val() << endl; }