#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;
set<pair<ll,int>> s;
void adauga(pair<ll,int> x)
{
s.insert(x);
}
void sterge(pair<ll,int> x)
{
s.erase(x);
}
pair<ll,int> getmin()
{
auto it = s.begin();
return *it;
}
ll dp[2500005];
int put23[2500005];
int a[2500005];
int solve(int n, int k, int* v)
{
dp[0]=0;
deque<pair<int,int>> dq;
dq.push_back({0,0});
a[0]=0;
adauga({0,0});
ll rez = 0;
put23[0]=1;
for(int i=1;i<=n;i++)
put23[i]=(put23[i-1]*23LL)%MOD;
for(int i=1;i<=n;i++)
{
a[i]=v[i-1];
if(!dq.empty() && i-dq.front().first>k)
{
pair<int,int> x = dq.front();
sterge({dp[dq.front().first]+dq.front().second, dq.front().first});
dq.pop_front();
if(dq.empty() || dq.front().first > x.first+1)
{
dq.push_front({x.first+1,x.second});
adauga({dp[x.first+1]+x.second, x.first+1});
}
}
dp[i]=INF;
int ult=-1;
while(!dq.empty() && dq.back().second<a[i])
{
ult=dq.back().first;
sterge({dp[dq.back().first]+dq.back().second, dq.back().first});
dq.pop_back();
}
if(ult!=-1 && (dq.empty() || dq.back().second>a[i]))
{
dq.push_back({ult,a[i]});
adauga({dp[ult]+a[i],ult});
}
/*cout<<i<<"\n";
for(int j=0;j<dq.size();j++)
cout<<dq[j].first<<" "<<dq[j].second<<"\n";
cout<<"\n\n";*/
dp[i] = getmin().first;
dq.push_back({i,0});
adauga({dp[i]+0,i});
//cout<<i<<" "<<dp[i]<<" zzz\n";
rez = (rez + ((dp[i]%MOD)*put23[n-i])%MOD)%MOD;
}
return rez;
}
/**
dp[i] = min(dp[j] + max(j+1..i))
*/
