#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "peru.h"
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 25e5 + 5;
const ll oo = 1e18 + 9;
const int mod = 1e9 + 7;
ll dp[MAX];
int* arr;
multiset<ll> st;
deque<int> q;
void erase_front(){
if(q.size() >= 2){
int a = q[0];
int b = q[1];
st.erase(st.find(dp[b] + arr[a]));
}
q.pop_front();
}
void erase_back(){
int a = q[q.size() - 1];
int b = q[q.size() - 2];
st.erase(st.find(dp[a] + arr[b]));
q.pop_back();
}
void insert(int a){
q.push_front(a);
if(q.size() > 1){
int b = q[1];
st.insert(dp[b] + arr[a]);
}
}
int solve(int n, int k, int* v){
arr = v;
q.push_front(0);
dp[0] = arr[0];
for (int i = 1; i < k; i++)
{
while(q.size() && arr[q.front()] <= arr[i]){
erase_front();
}
insert(i);
dp[i] = arr[q.back()];
}
for (int i = k; i < n; i++)
{
while(q.size() && arr[q.front()] <= arr[i]){
erase_front();
}
insert(i);
if(q.back() + k - 1 < i){
erase_back();
}
dp[i] = dp[i - k] + arr[q.back()];
if(st.size()){
dp[i] = min(dp[i], *st.begin());
}
}
ll ans = 0;
for (int i = 0; i <= n - 1; i++)
{
ans = (ans * 23 + dp[i]) % mod;
}
return ans;
}
