#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define pl pair<ll, ll>
#define f1 first
#define s2 second
const int MAX = 25e5 + 7;
const int mod = 1e9 + 7;
inline int add(ll x, ll y) { return (int)((x + y) % mod); }
inline int mul(ll x, ll y) { return (int)((x * y) % mod); }
struct Item {int mx, l, r; };
ll dp[MAX];
static int dq_l = 1, dq_r = 0;
Item dq[MAX];
int solve(int n, int k, int* v){
priority_queue<ll, vector<ll>, greater<ll>> pq, pending;
dp[0] = v[0];
dq[++dq_r] = {v[0], 0, 0};
pq.push(v[0]);
for (int i = 1; i < n; ++i)
{
//remove the front
if (dq_l <= dq_r && dq[dq_l].l <= i-k)
{
//int mx = dq[dq_l].mx, l = dq[dq_l].mx, r = dq[dq_l].r;
auto [mx, l, r] = dq[dq_l];
dq_l++;
pending.push(mx + (l ? dp[l-1] : 0));
if (r > i-k)
{
dq[--dq_l] = {mx, i-k+1, r};
pq.push(mx + (i-k+1 ? dp[i-k] : 0));
}
}
int cur_l = i, cur_r = i;
while (dq_l <= dq_r && dq[dq_r].mx <= v[i])
{
//int mx = dq[dq_r].mx, l = dq[dq_r].l, r = dq[dq_r].r;
auto [mx, l, r] = dq[dq_r];
dq_r--;
pending.push(mx + (l ? dp[l-1] : 0));
cur_l = l;
}
dq[++dq_r] = {v[i], cur_l, cur_r};
pq.push(v[i] + (cur_l ? dp[cur_l-1] : 0));
while (!pending.empty())
{
if (pq.top() > pending.top())
pending.pop();
else if (pq.top() < pending.top())
break;
else pq.pop(), pending.pop();
}
dp[i] = pq.top();
}
int pwr = 1, ans = 0;
for (int i = n-1; i >= 0; --i)
ans = add(ans, mul(dp[i]%mod, pwr)), pwr = mul(pwr, 23);
return ans;
}
