#include "peru.h"
#include <bits/stdc++.h>
#define ll long long
#define oo 1e17
#define pii pair<int, int>
using namespace std;
const int MAX = 25e5 + 5, MOD = 1e9 + 7;
ll arr[MAX];
ll dp[MAX];
ll val[MAX];
priority_queue<pair<ll, int>> s;
bool d[MAX];
deque<int> dq;
void clearQ(){
while(d[s.top().second]){
s.pop();
}
}
int solve(int n, int k, int* v){
for(int i = 0; i < n; i++){
arr[i + 1] = v[i];
}
dq.push_back(1);
dp[1] = arr[1];
for(int i = 2; i <= n; i++){
while(dq.size() && arr[dq.back()] <= arr[i]){
if(dq.size() > 1) d[dq.back()] = 1;
dq.pop_back();
}
if(dq.size() && dq.front() == i - k){
dq.pop_front();
if(dq.size()){
d[dq.front()] = 1;
}
}
dp[i] = oo;
if(dq.size()){
val[i] = dp[dq.back()] + arr[i];
s.push({-val[i], i});
clearQ();
dp[i] = -s.top().first;
}
dq.push_back(i);
dp[i] = min(dp[i], arr[dq.front()] + dp[max(0, i - k)]);
}
ll ans = 0;
for(int i = 1; i <= n; i++){
ans *= 23;
ans += dp[i];
ans %= MOD;
}
return ans;
}
