#include "peru.h"
#include "queue"
#include "set"
using namespace std;
int mod = 1e9 + 7;
long long binpow(int base, int exp) {
if (exp == 0) return 1;
long long half = binpow(base, exp / 2);
long long almost = half * half % mod;
if (exp % 2) almost = almost * base % mod;
return almost;
}
int solve(int n, int k, int* v){
deque<int> q;
int sum = 0;
long long power = 1;
for (int i = 0; i < n - 1; ++i) power = power * 23 % mod;
vector<long long> dp(n);
multiset<long long> ms;
int inv = binpow(23, mod - 2);
for (int i = 0; i < n; ++i) {
while (!q.empty()) {
int f = q.front();
if (v[f] <= v[i]) {
ms.extract((f? dp[f - 1]: 0) + v[f]);
q.pop_front();
} else {
break;
}
}
if (!q.empty() && q.back() == i - k) {
int b = q.back();
ms.extract((b? dp[b - 1]: 0) + v[b]);
q.pop_back();
}
ms.insert((i? dp[i - 1]: 0) + v[i]);
dp[i] = min(*ms.begin(), (i? q.empty()? i < k? 0: dp[i - k]: dp[i - 1]: 0) + v[i]);
q.push_front(i);
long long here = dp[i] * power % mod;
int cast_here = here;
sum = (sum + cast_here) % mod;
power = power * inv % mod;
}
return sum;
}
