MDN Editorialist

#include<bits/stdc++.h>

using namespace std;

const int MX = (1<<20);

typedef long long ll;

int n , M , K , arr[MX];

int dp[2][105][55];

int MOD = 1e9 + 7;

int main(){

    scanf("%d %d %d",&n,&K,&M);

    for(int j = 1 ; j <= n ; j++){
        scanf("%d",&arr[j]);
    }

    for(int j = 1 ; j <= n ; j++){
        if(arr[j] >= M) arr[j] = 1;
        else arr[j] = 0;
    }

    dp[0][0][0] = 1;

    int cur = 1;

    long long ans = 0;

    int upper = 51;

    for(int pos = 1 ; pos <= n ; pos++){

        dp[cur][0][0] = dp[cur^1][0][0];

        dp[cur][1][0] = dp[cur^1][1][0];

        dp[cur][1][1] = dp[cur^1][1][1];

        dp[cur][1][arr[pos]] += pos; dp[cur][1][arr[pos]] %= MOD;

        for(int take = 2 ; take <= min(pos , K) ; take++){

            for(int sum = 0 ; sum < upper ; sum++){

                dp[cur][take][sum] = dp[cur^1][take][sum];

                dp[cur][take][sum] += dp[cur^1][take - 1][sum - arr[pos]];

                dp[cur][take][sum] %= MOD;
            }


            if(take >= upper){

                dp[cur][take][upper] = dp[cur^1][take][upper];


                dp[cur][take][upper] += dp[cur^1][take - 1][upper];
                dp[cur][take][upper] %= MOD;


                if(arr[pos] == 1)
                    dp[cur][take][upper] += dp[cur^1][take - 1][upper - arr[pos]];

                dp[cur][take][upper] %= MOD;
            }

        }


        for(int take = (K + 1)/2 ; take <= min(K , upper) ; take++){
            long long theta = dp[cur][K][take] - dp[cur^1][K][take];
            theta += MOD; theta %= MOD;
            theta *= (n - pos + 1);
            theta %= MOD;
            ans += theta;
            ans %= MOD;
        }

        cur ^= 1;
    }

    cout<<ans<<endl;

}