#include "bits/stdc++.h"
using namespace std;
#include "peru.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
#define int long long
#define i32 int32_t
const int N = 25e5 + 5;
const int mod = 1e9 + 7;
const int P = 23;
int dp[N];
i32 solve(i32 n, i32 k, i32* a){
deque<i32> ss;
multiset<int> mm;
i32 res = 0;
for(int i=0;i<n;i++){
while(!ss.empty() && ss.front() <= i - k){
int j = ss.front(); ss.pop_front();
if(!ss.empty()){
mm.erase(mm.find(dp[j] + a[ss.front()]));
}
}
while(!ss.empty() && a[ss.back()] <= a[i]){
int j = ss.back(); ss.pop_back();
if(!ss.empty()){
mm.erase(mm.find(dp[ss.back()] + a[j]));
}
}
dp[i] = 1e18;
if(!ss.empty()) mm.insert(dp[ss.back()] + a[i]);
ss.push_back(i);
if(!mm.empty()) dp[i] = *mm.begin();
assert(!ss.empty());
dp[i] = min(dp[i], (i < k ? 0ll : dp[i-k]) + a[ss.front()]);
res = (res * 1ll * P + dp[i]) % mod;
}
//~ cout<<"\n";
return res;
}
