#include <bits/stdc++.h>

#include "peru.h"

using namespace std; const int maxn = 2.5e6 + 5, mod = 1e9 + 7; typedef long long ll;

ll tr[maxn << 2], tg[maxn << 2];

inline void C(int u, ll k) { tr[u] += k, tg[u] += k; }

inline void spread(int u) { C(u << 1, tg[u]), C(u << 1 | 1, tg[u]), tg[u] = 0; }

void update(int u, int l, int r, int ul, int ur, ll k)
{
    if (ul <= l && r <= ur) return C(u, k); int mid = l + r >> 1; spread(u);
    if (ul <= mid) update(u << 1, l, mid, ul, ur, k); if (ur > mid) update(u << 1 | 1, mid + 1, r, ul, ur, k);
    tr[u] = min(tr[u << 1], tr[u << 1 | 1]);
}

ll ask(int u, int l, int r, int ul, int ur)
{
    if (ul <= l && r <= ur) return tr[u]; int mid = l + r >> 1; spread(u); ll res = 1e18;
    if (ul <= mid) res = min(res, ask(u << 1, l, mid, ul, ur));
    if (ur > mid) res = min(res, ask(u << 1 | 1, mid + 1, r, ul, ur)); return res;
}

ll X[maxn];

int sk[maxn], tp;

int solve(int n, int k, int* v)
{
    sk[tp = 0] = -1;
    for (int i = 0; i < n; i++)
    {
        while (tp && v[sk[tp]] <= v[i]) update(1, 0, n, sk[tp - 1] + 1, sk[tp], v[i] - v[sk[tp]]), tp--;
        // update(1, 0, n, i, i, v[i]);
        sk[++tp] = i;
        X[i] = ask(1, 0, n, max(0, i - k + 1), i);
        if (i + 1 < n)
        update(1, 0, n, i + 1, i + 1, X[i] + v[i + 1]);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans = (23ll * ans + X[i]) % mod;
    // for (int i = 0; i < n; i++) cerr << X[i] << ' '; cerr << endl;
    return ans;
}