#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, MOD = 1e9 + 7;
ll arr[MAX];
ll dp[MAX];
ll val[MAX];
multiset<ll> s;
deque<int> dq;
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) s.erase(s.find(val[dq.back()]));
dq.pop_back();
}
if(dq.size() && dq.front() == i - k){
dq.pop_front();
if(dq.size()){
s.erase(s.find(val[dq.front()]));
}
}
dp[i] = oo;
if(dq.size()){
val[i] = dp[dq.back()] + arr[i];
s.insert(val[i]);
dp[i] = *s.begin();
}
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;
}
