#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
int add(int x, int y) {
return x + y < md ? x + y : x + y - md;
}
int mul(int x, int y) {
return x * 1LL * y % md;
}
int solve(int n, int k, int* v) {
vector<int> ft(n);
deque<int> dq;
for (int i = 0; i < n; i++) {
while (!dq.empty() && v[i] >= v[dq.back()]) {
dq.pop_back();
}
while (!dq.empty() && i - dq.front() + 1 > k) {
dq.pop_front();
}
dq.push_back(i);
ft[i] = v[dq.front()];
}
const long long inf = (long long) 1e18;
vector<long long> dp(n, inf);
multiset<pair<long long, int>> st;
vector<array<int, 3>> stk;
for (int i = 0; i < n; i++) {
int border = i;
while (!stk.empty() && v[i] > stk.back()[0]) {
border = stk.back()[1];
st.erase({(border == 0 ? 0LL : dp[border - 1]) + stk.back()[0], border});
stk.pop_back();
}
stk.push_back({v[i], border, i});
st.emplace((border == 0 ? 0LL : dp[border - 1]) + v[i], border);
while (!st.empty() && i - st.begin()->second + 1 > k) {
st.erase(st.begin());
}
if (!st.empty()) {
dp[i] = min(dp[i], st.begin()->first);
}
int j = max(0, i - k + 1);
dp[i] = min(dp[i], (j == 0 ? 0LL : dp[j - 1]) + ft[i]);
}
int res = 0;
int pw = 1;
for (int i = n - 1; i >= 0; i--) {
dp[i] %= md;
res = add(res, mul(pw, dp[i]));
pw = mul(pw, 23);
}
return res;
}
