#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;
const int mod = 1e9+7;
struct Stack {
stack<pair<ll, ll>> st;
ll getmin() {return st.top().second;}
bool empty() {return st.empty();}
int size() {return st.size();}
void push(ll x) {
ll mn = x;
if (!empty()) mn = min(mn, getmin());
st.push({x, mn});
}
void pop() {st.pop();}
ll top() {return st.top().first;}
void swap(Stack &x) {st.swap(x.st);}
};
struct Deque{
Stack l, r, t;
void rebalance() {
bool f = false;
if (r.empty()) {f = true; l.swap(r);}
int sz = r.size() / 2;
while (sz--) {t.push(r.top()); r.pop();}
while (!r.empty()) {l.push(r.top()); r.pop();}
while (!t.empty()) {r.push(t.top()); t.pop();}
if (f) l.swap(r);
}
ll getmin() {
if (l.empty()) return r.getmin();
if (r.empty()) return l.getmin();
return min(l.getmin(), r.getmin());
}
bool empty() {return l.empty() && r.empty();}
int size() {return l.size() + r.size();}
void push_front(ll x) {l.push(x);}
void push_back(ll x) {r.push(x);}
void pop_front() {if (l.empty()) rebalance(); l.pop();}
void pop_back() {if (r.empty()) rebalance(); r.pop();}
ll front() {if (l.empty()) rebalance(); return l.top();}
ll back() {if (r.empty()) rebalance(); return r.top();}
void swap(Deque &x) {l.swap(x.l); r.swap(x.r);}
};
int solve(int N, int K, int* S){
for(int i = N; i; i--) S[i] = S[i-1];
S[0] = 0;
vector<ll> dp(N+1,0);
deque<int> dq;
Deque st;
dp[1] = S[1];
dq.push_back(1);
st.push_back(dp[1]);
for(int i = 2; i <= N; i++){
int j = dq.front();
dq.pop_front(); st.pop_front();
if(j != i-K){
dq.push_front(j);
st.push_front(dp[max(0,i-K)] + S[j]);
}
while(!dq.empty() && S[dq.back()] <= S[i]){
dq.pop_back(); st.pop_back();
}
if(dq.empty()){
dq.push_back(i);
st.push_back(dp[max(0,i-K)]+S[i]);
}else{
st.push_back(dp[dq.back()]+S[i]);
dq.push_back(i);
}
dp[i] = st.getmin();
}
int ans = 0, mtp = 1;
for(int i = N; i; i--){
ans += (dp[i]%mod)*mtp%mod;
if(ans >= mod) ans -= mod;
mtp = mtp*23ll%mod;
}
return ans;
}
