#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
const ll inf = 1e18;
ll st[1<<20], lz[1<<20];
void push(int i){
if(lz[i]!=0){
st[i<<1|1] += lz[i], lz[i<<1|1] += lz[i];
st[i<<1] += lz[i], lz[i<<1] += lz[i]; lz[i] = 0;
}
}
void update(int i, int l, int r, int s, int e, ll val){
if(r < s || l > e) return;
if(s <= l && r <= e){
st[i] += val; lz[i] += val; return;
}
push(i); int m = (l+r)>>1;
update(i<<1,l,m,s,e,val);
update(i<<1|1,m+1,r,s,e,val);
st[i] = min(st[i<<1],st[i<<1|1]);
}
void add(int i, int l, int r, int k, ll val){
if(l==r){st[i]=val; return;}
push(i); int m = (l+r)>>1;
if(k <= m) add(i<<1,l,m,k,val);
else add(i<<1|1,m+1,r,k,val);
st[i] = min(st[i<<1],st[i<<1|1]);
}
ll get(int i, int l, int r, int s, int e){
if(r < s || l > e) return inf;
if(s <= l && r <= e) return st[i];
push(i); int m = (l+r)>>1;
return min(get(i<<1,l,m,s,e),get(i<<1|1,m+1,r,s,e));
}
int solve(int N, int K, int* S){
for(int i = N; i; i--) S[i] = S[i-1];
S[0] = INT_MAX;
vector<ll> dp(N+1,0);
vector<int> sta = {0};
for(int i = 1; i <= N; i++){
while(S[sta.back()] <= S[i]){
int r = sta.back(); sta.pop_back();
int l = sta.back();
update(1,1,N,l+1,r,-S[r]);
}
update(1,1,N,sta.back()+1,i,S[i]);
dp[i] = get(1,1,N,max(1,i-K+1),i);
if(i < N) add(1,1,N,i+1,dp[i]);
sta.push_back(i);
}
int ans = 0, mtp = 1;
for(int i = N; i; i--){
ans += (dp[i]%mod)*mtp%mod;
if(ans >= mod) ans -= mod;
mtp = 1ll*mtp*23%mod;
}
return ans;
}
