TOI19 Energy

#include<bits/stdc++.h>
#define endl "\n";
#define MOD (ll )(1e9+7)
using ll = long long;
using namespace std;
int dp[1010],k,d,n;
ll memo[310][310][12];
ll mcm(int l,int r,int lev){
    if(memo[l][r][lev] != -1)
        return memo[l][r][lev];
    int cnt=0;
    if(lev == k-1){
        for(int i=l;i<r;i++){
            if(abs((dp[r]-dp[i]) - (dp[i]-dp[l-1])) <= d){
                cnt++;
            }
        }
        return cnt;
    }
    ll ret = 0;
    for(int i=l;i<r;i++){
        if(abs((dp[r]-dp[i]) - (dp[i]-dp[l-1])) <= d){
            ret+=(mcm(l,i,lev+1)*mcm(i+1,r,lev+1))%MOD;
            ret%=MOD;
        }
    }
    return memo[l][r][lev] = ret;
}
int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin>>n>>k>>d;
    for(int i=1;i<=n;i++){
        cin>>dp[i];
        dp[i]+=dp[i-1];
    }
    memset(memo,-1,sizeof memo);
    cout<<mcm(1,n,1);
    return 0;
}