#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
constexpr int MOD = 1000000007;
signed solve(signed n, signed k, signed* v){
vector<int> tt(n, 1);
for(int i = 1; i < n; i ++) tt[i] = (tt[i - 1] * 23) % MOD;
vector<int> dp(n);
dp[0] = v[0];
deque<int> ind = {0};
set<int> dps{};
int ans = 0;
ans += dp[0] * tt[n - 1];
for(int i = 1; i < n; i ++) {
while(!ind.empty() && v[ind.back()] < v[i]) {
if(ind.size() > 1) dps.erase(v[ind.back()] + dp[ind[ind.size() - 2]]);
ind.pop_back();
}
if(!ind.empty()) dps.insert(v[i] + dp[ind.back()]);
ind.push_back(i);
if(ind.front() <= i - k) {
dps.erase(dp[ind[0]] + v[ind[1]]);
ind.pop_front();
}
if(i - k >= 0) dps.insert(dp[i - k] + v[ind.front()]);
else dps.insert(v[ind.front()]);
dp[i] = *dps.begin();
ans += (dp[i] % MOD) * tt[n - i - 1];
ans %= MOD;
if(i - k >= 0) dps.erase(dp[i - k] + v[ind.front()]);
else dps.erase(v[ind.front()]);
}
return ans;
}
