#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
using i64 = long long;
const int MOD = 1e9 + 7;
i64 add(i64 x,i64 y){
return (x + y) % MOD;
}
i64 mul(i64 x,i64 y){
return (x % MOD * (y % MOD)) % MOD;
}
int solve(int n, int k, int* v){
vector<i64> dp(n + 10,1e18);
for (int i = 0; i < n; i++){
i64 mx = -1e18;
for (int j = 0; j < k; j++){
int old;
if (i - j - 1 < 0) old = 0;
else old = dp[i - j - 1];
if (i - j > -1) mx = max(mx,(i64) v[i - j]);
dp[i] = min(dp[i],(i64) old + mx);
}
}
i64 ans = 0,pw = 1;
for (int i = n-1; i > -1; i--){
ans = add(ans,mul(dp[i],pw));
pw = mul(pw,23);
}
return ans;
}
