#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const ll inf = 4e18;
const ll mod = 1e9+7;
const ll p = 23;
const int mxn = 2500001;
int sparse[21][mxn];
int arr[mxn];
deque<int> dq;
pll dp[mxn];
void build(int N){
for(int i = 0;i<=N;i++){
sparse[0][i] = arr[i];
}
for(int i = 1;i<21;i++){
for(int j = 0;j+(1<<i)-1<=N;j++){
sparse[i][j] = max(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);
}
}
return;
}
int getval(int l,int r){
int h = __lg(r-l+1);
return max(sparse[h][l],sparse[h][r-(1<<h)+1]);
}
const int magic = 1000;
int solve(int N,int K,int* S){
int s = clock();
int lim = 0.010*CLOCKS_PER_SEC;
for(int i = N;i>=1;i--)arr[i] = S[i-1];
arr[0] = 0;
build(N);
if(clock()-s>=lim)return 0;
dp[0] = make_pair(0,0);
ll re = 0;
for(int i = 1;i<=N;i++){
dp[i] = make_pair(inf,i);
for(int j = i-1;i-j<=K&&j>=0&&i-j<=magic;j--){
dp[i] = min(dp[i],make_pair(dp[j].fs+getval(j+1,i),1ll*j));
}
for(int C = 0, j = max(dp[i-1].sc,1ll*i-K);C<=magic&&j<i;C++,j++){
dp[i] = min(dp[i],make_pair(dp[j].fs+getval(j+1,i),1ll*j));
}
dp[i].sc = max(dp[i].sc,dp[i-1].sc);
re = (re*p+dp[i].fs)%mod;
}
//for(int i = 1;i<=N;i++)cout<<dp[i].fs<<' ';cout<<endl;
return re;
}
/*
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i = 0;i<n;i++)cin>>arr[i];
cout<<solve(n,k,(int*)arr);
}
*/
