// Your arson's match, your somber eyes
// And I'll still see it until I die
// You're the loss of my life
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7, base = 23;
void upd(int& a, int b) { a = (a + b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
const int maxn = 1 << 22;
ll st[maxn * 2], lz[maxn * 2];
int l[maxn * 2], r[maxn * 2];
void update(int li, int ri, ll x, int vr = 1)
{
if (ri < l[vr] || r[vr] < li) return;
if (li <= l[vr] && r[vr] <= ri) return st[vr] += x, lz[vr] += x, void();
update(li, ri, x, vr << 1), update(li, ri, x, (vr << 1) | 1);
st[vr] = min(st[vr * 2], st[vr * 2 + 1]) + lz[vr];
}
ll query(int li, int ri, int vr = 1)
{
if (ri < l[vr] || r[vr] < li) return 1e18;
if (li <= l[vr] && r[vr] <= ri) return st[vr];
return min(query(li, ri, (vr << 1)), query(li, ri, (vr << 1) | 1)) + lz[vr];
}
ll dp[maxn], s[maxn];
vector<int> mq;
int solve(int n, int k, int* S)
{
for (int i = maxn; i < maxn * 2; i++) l[i] = r[i] = i - maxn;
for (int i = maxn - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
for (int i = 0; i < n; i++) s[i] = S[i];
mq.push_back(-1);
for (int i = 1; i <= n; i++) // ideme postavit prefix dlzky i
{
while (mq.size() > 1 && s[mq.back()] < s[i - 1]) update(mq[mq.size() - 2] + 1, mq.back(), s[i - 1] - s[mq.back()]), mq.pop_back();
update(i - 1, i - 1, dp[i - 1] + s[i - 1]);
mq.push_back(i - 1);
dp[i] = query(max(0, i - k), i - 1);
//cout << i << " : " << dp[i] << "\n";
}
int ans = 0, m = 1;
for (int i = n; i >= 1; i--) upd(ans, mul(dp[i] % (ll)mod, m)), m = mul(m, base);
return ans;
}
