#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
const int mod = 1e9+7;
int solve(int N, int K, int* S) {
vector<long long> dp(N+1, 0);
long long ans = 0;
for (int i = 0; i < N; i++) {
dp[i+1] = dp[i]+S[i];
int e = S[i];
for (int j = i-1; j > max(-1, i-K); j--) {
e = max(e, S[j]);
dp[i+1] = min(dp[i+1], dp[j]+e);
}
//~ cout << dp[i+1] << endl;
ans = ((long long)ans*23)%mod;
ans = (ans+dp[i+1])%mod;
}
//~ cout << ans << endl;
return ans;
}
//~ signed main() {
//~ ios::sync_with_stdio(false);
//~ cin.tie(0);
//~ cout.tie(0);
//~ vector<int> tmp = {3, 2, 9, 8, 7, 11, 3, 4};
//~ solve(8, 3, tmp);
//~ }
