#include "peru.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1e9 + 7;
constexpr ll infLL = 3e18;

struct Heap {
    priority_queue<ll, vector<ll>, greater<>> ins, del;
    void insert(ll x) { ins.push(x); }
    void erase(ll x) { del.push(x); }
    ll top() {
        while (!del.empty() && ins.top() == del.top()) {
            ins.pop(), del.pop();
        }
        return ins.empty() ? infLL : ins.top();
    }
};

constexpr int N = 2.5e6 + 7;

ll dp[N];
int stk[N], stkFront = 0, stkBack = 0;
//ll deq[N], deqFront = 0, deqBack = 0;

int solve(int n, int k, int a[]){
    int ans = 0;
//    Heap h;
    for (int i = 0; i < n; ++i) {
        if (stkFront < stkBack && stk[stkFront] <= i - k) {
//            h.erase(dp[stk[stkFront]] + a[stk[stkFront + 1]]);
            stkFront += 1;
//            deqFront = min(deqFront + 1, deqBack);
        }
        while (stkBack > stkFront && a[stk[stkBack - 1]] <= a[i]) {
            if (stkBack - 2 >= stkFront) {
//                h.erase(dp[stk[stkBack - 2]] + a[stk[stkBack - 1]]);
            }
            stkBack -= 1;
        }
        if (stkFront < stkBack) {
//            h.insert(dp[stk[stkBack - 1]] + a[i]);
        }
        stk[stkBack++] = i;
        ll mn = 3e18;
        for (int c = 0; c < min(10, stkBack - stkFront - 1); ++c) {
            mn = min(mn, a[stk[stkBack - c - 1]] + dp[stk[stkBack - c - 2]]);
        }
        for (int c = stkBack - stkFront - 2, cnt = 0; c >= 0 && cnt < 10; --c, ++cnt) {
            mn = min(mn, a[stk[stkBack - c - 1]] + dp[stk[stkBack - c - 2]]);
        }
        int j = stk[stkFront];
        dp[i] = min(/*h.top()*/mn, a[j] + (i - k >= 0 ? dp[i - k] : 0));
        ans = (23LL * ans + dp[i]) % MOD;
//        cout << dp[i] << " ";
    }
//    cout << endl;
    return ans;
}