#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 25e5;
const ll inf = 1e17, mod = 1e9 + 7;
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;
deque<pair<int,int>> se;
set<ll> mn;
se.push_back({0,0});
for (int i=0;i<n;i++)
{
int prv;
while (!se.empty())
{
pair<int,int> p=se.back();
if (p.second>a[i]) break;
prv=p.first;
if (prv<i && prv>=i-k && prv)
mn.erase(dp[prv-1]+p.second);
se.pop_back();
}
se.push_back({prv,a[i]});
if (prv)
mn.insert(dp[prv-1]+a[i]);
pair<int,int> ls=se.front();
while (se.size())
{
pair<int,int> p=se.front();
if (p.first<=i-k)
{
if (p.first) mn.erase(dp[p.first-1]+p.second);
se.pop_front();
ls=p;
}
else
break;
}
if (se.empty() or se.front()!=ls)
se.push_front(ls);
if (i>=k)
{
ll m=inf;
if (mn.size()) m=*mn.begin();
ls=se.front();
int mx=max(ls.first-1,i-k);
m=min(m,dp[mx]+ls.second);
dp[i]=m;
}
se.push_back({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;
}
