#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int solve(int n, int k, int* v){
deque<int> dq;
set<pair<ll,int>> st;
vector<ll> dp(n, 0), cand(n, 0);
for(int i=0;i<n;i++){
while(!dq.empty() and dq.front() <= i-k){
st.erase({cand[dq.front()], dq.front()});
dq.pop_front();
}
while(!dq.empty() and v[dq.back()] <= v[i]){
st.erase({cand[dq.back()], dq.back()});
dq.pop_back();
}
if(dq.empty()){
cand[i]=(i-k >= 0? dp[i-k]:0)+v[i];
}
else {
st.erase({cand[dq.front()], dq.front()});
cand[dq.front()]=(i-k>=0?dp[i-k]:0)+v[dq.front()];
st.insert({cand[dq.front()],dq.front()});
cand[i]=dp[dq.back()]+v[i];
}
st.insert({cand[i], i});
dp[i]=(*st.begin()).first;
dq.push_back(i);
printf("i %d, cand %lld, dp %lld\n", i, cand[i], dp[i]);
}
ll ans=0, mul=1;
for(int i=n-1;i>=0;i--){
ans=(ans+mul*dp[i]%mod)%mod;
mul=mul*23%mod;
}
return ans;
}
/*
5 2
2000000000 2000000000 2000000000 2000000000 2000000000
*/
