#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);
}
struct apdeit
{
int l;
int r;
int numar;
};
int dp[2500005];
signed S[2500005];
int v[2500005];
apdeit st[2500005];///avem o stiva cu updateurile, care e defapt stiva pentru cost (elemente mai mari/mai mici)
const int mod=1e9+7;
struct Node
{
int lazy;
int minval;
};
class AINT
{
public:
Node aint[10000005];
void build(int l, int r, int val)
{
if (l==r)
{
if (l==0)
aint[val].minval=0;
else
aint[val].minval=1e18;
aint[val].lazy=0;
return;
}
int mid;
mid=(l+r)/2;
build(l,mid,val*2);
build(mid+1,r,val*2+1);
aint[val].minval=1e18;
aint[val].lazy=0;
}
void prop(int val, int l, int r)
{
if (aint[val].lazy==0)
return;
aint[val].minval+=aint[val].lazy;
if (l!=r)
{
aint[val*2].lazy+=aint[val].lazy;
aint[val*2+1].lazy+=aint[val].lazy;
}
aint[val].lazy=0;
}
void small_update(int l, int r, int val, int poz, int x)
{
prop(val,l,r);
if (l==r && l==poz)
{
aint[val].minval=x;
return;
}
int mid;
mid=(l+r)/2;
if (poz<=mid)
small_update(l,mid,val*2,poz,x);
else
small_update(mid+1,r,val*2+1,poz,x);
prop(val*2,l,mid);
prop(val*2+1,mid+1,r);
aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
}
void lazy_update(int l, int r, int val, int qa, int qb, int x)
{
prop(val,l,r);
if (qa<=l && r<=qb)
{
aint[val].lazy+=x;
return;
}
int mid;
mid=(l+r)/2;
if (qa<=mid)
lazy_update(l,mid,val*2,qa,qb,x);
if (qb>mid)
lazy_update(mid+1,r,val*2+1,qa,qb,x);
prop(val*2,l,mid);
prop(val*2+1,mid+1,r);
aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
}
int query(int l, int r, int val, int qa, int qb)
{
prop(val,l,r);
if (qa<=l && r<=qb)
{
return aint[val].minval;
}
int ans,mid;
ans=1e18;
mid=(l+r)/2;
if (qa<=mid)
ans=min(ans,query(l,mid,val*2,qa,qb));
if (qb>mid)
ans=min(ans,query(mid+1,r,val*2+1,qa,qb));
return ans;
}
} aint;
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,t;
n=N;
k=K;
ans=0;
for (i=1;i<=n;i++)
{
v[i]=S[i-1];
}
aint.build(0,n,1);
t=0;
st[0].l=0;
st[0].r=0;
st[0].numar=0;
for (i=1;i<=n;i++)
{
while (t>0 && st[t].numar<=v[i])
{
aint.lazy_update(0,n,1,st[t].l,st[t].r-1,-st[t].numar);
t--;
}
t++;
st[t].l=st[t-1].r;
st[t].r=i;
st[t].numar=v[i];
aint.lazy_update(0,n,1,st[t].l,st[t].r-1,st[t].numar);
dp[i]=aint.query(0,n,1,max(0LL,i-k),i-1);
aint.small_update(0,n,1,i,dp[i]);
ans+=((dp[i]%mod)*lgpow(23,n-i))%mod;
ans%=mod;
}
return ans;
}
