#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 25e5, mod = 1e9 + 7;
const ll inf = 1e17;
ll dp[M];
int power(int a,int b)
{
int ans=1;
for (;b;b>>=1,a=1ll*a*a%mod)
if (b&1) ans=1ll*ans*a%mod;
return ans;
}
int solve(int n,int k,int* a)
{
int mx=0;
for (int i=0;i<k;i++)
mx=max(mx,a[i]),dp[i]=mx;
set<pair<int,int>> se;
multiset<int> mn;
se.insert({0,0});
for (int i=0;i<n;i++)
{
int prv;
while (!se.empty())
{
pair<int,int> p=*se.rbegin();
if (p.second>a[i]) break;
prv=p.first;
if (prv<i && prv>=i-k && prv)
mn.erase(mn.find(dp[prv-1]+p.second));
se.erase(p);
}
se.insert({prv,a[i]});
if (prv)
mn.insert(dp[prv-1]+a[i]);
pair<int,int> ls=*se.begin();
while (se.size())
{
auto it=se.begin();
pair<int,int> p=*it;
if (p.first<=i-k)
{
if (p.first) mn.erase(mn.find(dp[p.first-1]+p.second));
se.erase(p);
ls=p;
}
else
break;
}
se.insert(ls);
if (i>=k)
{
ll m=inf;
if (mn.size()) m=*mn.begin();
ls=*se.begin();
int mx=max(ls.first-1,i-k);
m=min(m,dp[mx]+ls.second);
dp[i]=m;
}
se.insert({i+1,0});
}
int inv=power(23,mod-2),val=1,ans=0;
for (int i=0;i<n-1;i++) val=1ll*val*23%mod;
for (int i=0;i<n;i++,val=1ll*val*inv%mod)
ans=(ans+dp[i]%mod*val%mod)%mod;
return ans;
}
