#include <bits/stdc++.h>
#include "peru.h"
// #include "grader.cpp"
using namespace std;
typedef long long ll;
const int N = 2.5e6 + 10, mod = 1e9 + 7;
int n, k, a[N], ngl[N];
ll p[N];
int solve(int nn, int kk, int* v){
n = nn, k = kk;
for (int i = 1; i <= n; i ++)
a[i] = v[i - 1];
stack<int> stk;
stk.push(0);
for (int i = 1; i <= n; i ++){
while (!stk.empty() and stk.top() != 0 and a[stk.top()] <= a[i])
stk.pop();
ngl[i] = stk.top();
stk.push(i);
}
deque<int> dq1, dq2;
dq1.push_back(0); dq2.push_back(0);
multiset<ll> st;
st.insert(0);
for (int i = 1; i <= n; i ++){
st.erase(st.find(p[max(i - k - 1, ngl[dq1[0]])] + a[dq1[0]]));
if (!dq1.empty() and dq1[0] <= i - k) dq1.pop_front();
else st.insert(p[max(i - k, ngl[dq1[0]])] + a[dq1[0]]);
while (!dq1.empty() and a[dq1.back()] <= a[i]){
st.erase(st.find(p[max(i - k, ngl[dq1.back()])] + a[dq1.back()]));
dq1.pop_back();
}
dq1.push_back(i);
st.insert(p[max(i - k, ngl[i])] + a[i]);
p[i] = *st.begin();
}
ll pw = 1, res = 0;
for (int i = n; i > 0; i --, pw = (23ll * pw) % mod)
res = (res + (1ll * (p[i] % mod) * pw % mod)) % mod;
return res;
}
