#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
#define ll long long
ifstream f("peru.in");
ofstream g("peru.out");
long long din[2500005];
long long min1(long long a,long long b)
{
if (a<b)
{
return a;
}
return b;
}
long long max1(long long a,long long b)
{
if (a>b)
{
return a;
}
return b;
}
long long arb[10000005];
long long lazy[10000005];
void propaga(int st,int dr,int nod)
{
if (st==dr)
{
return;
}
if (lazy[nod]==0)
{
return;
}
lazy[2*nod]+=lazy[nod];lazy[2*nod+1]+=lazy[nod];
arb[2*nod]+=lazy[nod];arb[2*nod+1]+=lazy[nod];
lazy[nod]=0;
return;
}
void update(int st ,int dr,int nod,int ua,int ub, long long val)
{
propaga(st,dr,nod);
if (ua<=st&&dr<=ub)
{
arb[nod]+=val;
lazy[nod]+=val;
return;
}
int mij=(st+dr)/2;
if (ua<=mij)
{
update(st,mij,2*nod,ua,ub,val);
}
if (mij<ub)
{
update(mij+1,dr,2*nod+1,ua,ub,val);
}
arb[nod]=min1(arb[2*nod],arb[2*nod+1]);
}
long long query(int st,int dr,int nod,int ua,int ub)
{
propaga(st,dr,nod);
if (ua<=st&&dr<=ub)
{
return arb[nod];
}
int mij=(st+dr)/2;
if (ub<=mij)
{
return query(st,mij,2*nod,ua,ub);
}
else
if (mij<ua)
{
return query(mij+1,dr,2*nod+1,ua,ub);
}
else
{
return min1(query(st,mij,2*nod,ua,ub),query(mij+1,dr,2*nod+1,ua,ub));
}
}
stack <int> st;
deque <pair <int,int> > maxime;
int stanga[2500005];
int solve(int n, int k, int* v)
{
long long put=1,maxim,i,j,suma=0,ceaules;
din[1]=v[0];
update(1,n,1,1,1,v[0]);
maxime.push_back({1,1});
for (i=2;i<=n;i++)
{
if (maxime.front().first<i-k+1)
{
maxime.front().first++;
if (maxime.front().first>maxime.front().second)
{
maxime.pop_front();
}
}
int acum=i;
while (!maxime.empty()&&v[maxime.back().second-1]<v[i-1])
{
acum=maxime.back().first;
update(1,n,1,maxime.back().first,maxime.back().second,v[i-1]-v[maxime.back().second-1]);
maxime.pop_back();
}
update(1,n,1,i,i,din[i-1]+v[i-1]);
maxime.push_back({acum,i});
int lim=max1(1,i-k+1);
din[i]=query(1,n,1,lim,i);
}
for (i=n-1; i>=0; i--)
{
suma=(suma+(1LL*put*(din[i+1]%MOD))%MOD)%MOD;
put=(1LL*23*put)%MOD;
}
return suma;
}
