#include "peru.h"
#include "bits/stdc++.h"
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
using i64 = long long;
constexpr i64 inf = i64(1E18);
constexpr int md = int(1E9) + 7;
struct SparseTable {
int n;
std::vector<int> logs;
std::vector<std::vector<int>> mat;
std::vector<int> v;
SparseTable(int n_, int* v_) : n(n_), v(n) {
for (int i = 0; i < n ; ++i) {
v[i] = v_[i];
}
init();
}
void init() {
logs.resize(n + 1, -1);
for (int i = 1; i <= n; ++i) {
logs[i] = logs[i >> 1] + 1;
}
int LG = logs[n];
mat.resize(LG + 1);
mat[0].resize(n);
for (int i = 0; i < n; ++i) {
mat[0][i] = i;
}
for (int i = 1; i <= LG; ++i) {
mat[i].resize(n - (1 << i) + 1);
for (int j = 0; j < n - (1 << i) + 1; ++j) {
mat[i][j] = std::min(mat[i - 1][j], mat[i - 1][j + (1 << (i - 1))], [&](auto lhs, auto rhs) {
return v[lhs] > v[rhs];
});
}
}
}
int get(int l, int r) {
int len = r - l + 1;
int lg = logs[len];
return std::min(mat[lg][l], mat[lg][r - (1 << lg) + 1], [&](auto lhs, auto rhs) {
return v[lhs] > v[rhs];
});
}
};
};
int solve(int N, int K, int* A){
std::vector<i64> f(N + 1, inf);
f[0] = 0;
for (int i = 1; i <= N; ++i) {
int mx = 0;
for (int j = i; j >= std::max(1, i - K + 1); --j) {
mx = std::max(mx, A[j - 1]);
f[i] = std::min(f[i], f[j - 1] + mx);
}
}
int ans = 0;
for (int i = 0; i < N; ++i) {
int x = f[i + 1] % md;
debug(i, x);
ans = (ans * 23LL + x) % md;
}
return ans;
}
