#include<bits/stdc++.h>
#include "peru.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
int dp[2500005];
signed S[2500005];
int v[2500005];
int dir[2500005];
deque<pair<int,int>> deqe;
const int mod=1e9+7;
const int inf=1e18;
class coada
{
public:
pair<int,int> fr[2500005];
int mif[2500005]={inf};
pair<int,int> bk[2500005];
int mib[2500005]={inf};
int tfr=0;///scuze
int tbk=0;///scuze
void push(int idxdp, int idxmx)
{
tbk++;
bk[tbk]= {idxdp,idxmx};
mib[tbk]=min(mib[tbk-1],dp[idxdp]+v[idxmx]);
}
void pop()
{
if (tfr==0)
{
while (tbk>0)
{
tfr++;
fr[tfr]=bk[tbk];
mif[tfr]=min(mif[tfr-1],dp[bk[tbk].first]+v[bk[tbk].second]);
tbk--;
}
}
if (fr[tfr].first<fr[tfr].second-1)
{
fr[tfr].first++;
mif[tfr]=min(mif[tfr-1],dp[fr[tfr].first]+v[fr[tfr].second]);
}
else
{
tfr--;
}
}
bool empti()
{
if (tfr+tbk==0)
return 1;
else
return 0;
}
pair<int,int> froont()
{
if (tfr!=0)
return fr[tfr];
else
return bk[1];
}
pair<int,int> bek()
{
if (tbk!=0)
return bk[tbk];
else
return fr[1];
}
int query_min()
{
int ans;
ans=min(mif[tfr],mib[tbk]);
return ans;
}
};
class dqSigma
{
public:
coada q;
pair<int,int> st[2500005];
int mi[2500005]={inf};
int t=0;///scuze din nou
void pop_bk()
{
t--;
}
void pop_fr()
{
q.pop();
}
void push_bk(int idxdp, int idxmx)
{
if (dir[idxmx]==1)
{
t++;
st[t]= {idxdp,idxmx};
mi[t]=min(mi[t-1],dp[idxdp]+v[idxmx]);
}
else
{
q.push(idxdp,idxmx);
}
}
bool empti()
{
if (q.empti() && t==0)
return 1;
else
return 0;
}
pair<int,int> fr()
{
if (!q.empti())
return q.froont();
else
return st[1];
}
pair<int,int> bk()
{
if (t!=0)
return st[t];
else
return q.bek();
}
int query_min()
{
int ans;
ans=min(q.query_min(),mi[t]);
return ans;
}
} dq;
int lgpow(int x, int p)
{
int ans,pw,i;
ans=1;
pw=x;
for (i=0; i<30; i++)
{
if (p&(1<<i))
ans=(ans*pw)%mod;
pw=(pw*pw)%mod;
}
return ans;
}
signed solve(signed N, signed K, signed* S)
{
int n,k,i,j,ans,imin;
n=N;
k=K;
for (i=1; i<=n; i++)
{
v[i]=S[i-1];
}
deqe.push_back({0,0});
for (i=1; i<=n; i++)
{
if (i!=1)
{
while (!deqe.empty() && deqe.front().first<i-k)
{
deqe.front().first++;
}
if (!deqe.empty() && deqe.front().first>=deqe.front().second)
{
dir[deqe.front().second]=0;
deqe.pop_front();
}
if (!deqe.empty())
assert(deqe.front().first>=i-k);
}
imin=i-1;
while (!deqe.empty() && v[deqe.back().second]<v[i])
{
imin=min(imin,deqe.back().first);
dir[deqe.back().second]=1;
deqe.pop_back();
}
deqe.push_back({imin,i});
}
deqe.clear();
dq.push_bk(0,0);
ans=0;
for (i=1; i<=n; i++)
{
if (i!=1)
{
while (!dq.empti() && dq.fr().first<i-k)
{
dq.pop_fr();///asta defapt imi incrementeaza first si in cazul in care nu e bine ii si da pop
}
if (!dq.empti())
assert(dq.fr().first>=i-k);
}
imin=i-1;
while (!dq.empti() && v[dq.bk().second]<v[i])
{
imin=min(imin,dq.bk().first);
dq.pop_bk();
}
dq.push_bk(imin,i);
dp[i]=dq.query_min();
ans+=((dp[i]%mod)*lgpow(23,n-i))%mod;
ans%=mod;
}
return ans;
}
