#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
int solve(int N, int K, int* S){
vector<ll> dp(N,0);
dp[0] = S[0];
for(int i = 1; i < N; i++){
int mx = S[i];
dp[i] = dp[i-1]+mx;
for(int j = i-1; j >= 0 && i-j <= K; j--){
dp[i] = min(dp[i],dp[j] + mx);
mx = max(mx,S[j]);
}
if(i < K) dp[i] = mx;
}
int mtp = 1, ans = 0;
for(int i = N-1; i >= 0; i--){
ans += 1ll*(dp[i]%mod)*mtp%mod;
if(ans >= mod) ans -= mod;
mtp = 1ll*mtp*23%mod;
}
return ans;
}
