#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){
SparseTable st(N, A);
std::vector<std::unordered_map<int, i64>> f(N);
auto dfs = [&](auto&& self, int l, int r) -> i64 {
if (r - l + 1 <= K) {
int mx = 0;
for (int i = l; i <= r; ++i) {
mx = std::max(mx, A[i]);
}
return mx;
}
if (f[r].count(l)) {
return f[r][l];
}
i64 res = inf;
int p = st.get(l, r);
debug(l, r, p);
for (int i = std::max(l, p - K + 1); i <= std::min(r - K + 1, p); ++i) {
res = std::min(res, self(self, l, i - 1) + self(self, i + 3, r) + A[p]);
}
return f[r][l] = res;
};
int ans = 0;
for (int i = 0; i < N; ++i) {
int x = dfs(dfs, 0, i) % md;
debug(i, x);
ans = (ans * 23LL + x) % md;
}
return ans;
}
